什么类型的语言被PDA接受,其中堆栈大小有限？

Question

什么类型的语言被PDA接受,其中堆栈大小限制为20项？

在我看来它应该仍然是CFL,因为有一个临时存储器存储.

Answer 1

堆栈限制为包含20个项目的PDA相当于DFA.这是证明.

1. 拿任何PDA-20,你可以把它变成一个等效的DFA.让我们说堆栈字母S在哪里| S | = N.你还有堆栈符号Z.我们想象一个额外的符号, - 我们也可以在堆栈上,代表"未使用".堆栈现在等效于x = - *S*Z形式的字符串,其中| x | 在所有情况下都是20.推入堆栈包括替换 - 的出现,而popping包括用LIFO方式替换其他符号.对于任何PDA-20,现在存在(N + 2)^ 20个堆栈的可能配置.要构造DFA,只需通过此因子复制DFA的每个状态,并且转换到DFA的状态将反映堆栈的新配置.这样,PDA-20中堆栈配置中包含的信息包含在DFA的当前状态中.

2. 拿任何DFA,你可以把它变成一个等效的PDA-20.只是不要使用堆栈,你有一个PDA-20,它接受与DFA相同的语言.

为了说明证明的第一部分,考虑具有状态A,B,C,......,Z和许多转换的PDA-5.假设输入字母是{0,1}.然后有2 ^ 5 = 32种不同的堆栈配置,比方说.相当于这个PDA-5的DFA可能具有状态A1,B1,......,Z1,A2,B2,......,Z2,...,A32,B32,...,Z32,尽管它将具有转换次数与原始转换次数相同.如果原始PDA-5中的转换将从状态R中的配置#2到配置#17以及机器到状态F的堆栈,则DFA将从状态R2进入状态F17.