栈容量至多为k个符号的PDA M所识别语言类型求证

你的判断完全正确，栈大小受限的PDA本质上等价于有限自动机，以下是严格证明：

证明过程 #

我们可以通过构造等价的确定有限自动机（DFA）来完成证明：

1. 确定DFA的状态集合
   设原PDA M的状态集合为$Q$，栈字母表为$\Gamma$。由于栈最多容纳k个符号，栈的可能内容是所有长度≤k的$\Gamma$上的字符串（包括空串$\epsilon$），记栈的可能状态集合为$S$。
   构造的DFA状态集合为$Q \times S$——每个DFA状态由PDA的当前状态和当前栈的完整内容组成。
   因为$Q$是有限集合，$S$的大小为$1 + |\Gamma| + |\Gamma|^2 + ... + |\Gamma|^k$，显然也是有限的，因此$Q \times S$是有限集合，满足DFA对状态数有限的要求。

2. 确定DFA的初始状态
   DFA的初始状态为$(q_0, \perp)$，其中$q_0$是PDA的初始状态，$\perp$是PDA的初始栈底符号（长度为1，不超过k的限制）。

3. 定义DFA的转移函数
   对于DFA中的任意状态$(q, s)$，以及输入符号$a$：
   原PDA M的转移函数为$\delta(q, a, top(s))$，其中$top(s)$是栈$s$的栈顶符号。对于每个转移结果$(q', s')$（即PDA从状态q读入a，弹出栈顶后压入新符号序列得到栈$s'$，且$s'$的长度≤k），我们在DFA中添加转移规则：$\delta_{DFA}((q, s), a) = (q', s')$。
   若PDA包含$\epsilon$转移（不读入输入符号），可先构造等价的非确定有限自动机（NFA），再通过子集构造法转为DFA，这一步不影响状态集合的有限性。

4. 确定DFA的接受状态
   DFA的接受状态集合为所有$(q, s)$，其中$q$是PDA的接受状态，或$q$与栈内容$s$共同满足原PDA的接受条件（比如空栈接受规则下，就是$s = \epsilon$且$q$为对应状态），完全匹配原PDA的接受逻辑。

等价性说明 #

构造出的DFA与原PDA M完全等价：

• 对于任意输入字符串$w$，PDA M处理$w$时的每一步状态和栈内容，都对应DFA处理$w$时的状态转移路径。
• 当PDA M接受$w$时，DFA会进入对应的接受状态；反之，若DFA接受$w$，则PDA M也必然接受$w$。

由于正则语言的定义是所有能被DFA识别的语言，因此L(M)属于正则语言。

内容的提问来源于stack exchange，提问作者beezzyy