证明该语言不受上下文限制

Question

我们如何为该语言设计PDA

L= {w | number of 010s in w is more than the number of 101s}

证明它是无背景的

Answer 1

您可以使用堆栈作为计数器，以获得010和101的数字之间的差异，直至您已读取的点。例如，您可以使用A计算010（如果它们已经更多）和B来计算101。

现在在你的州，你记得你见过的最后两个符号。如果与当前读取的符号一起形成010，您：

• 如果最顶层的堆栈符号是A或堆栈为空，则将A放在堆栈上。
• 否则从堆栈中删除B.

类似于101。

因此，当您完成读取输入时，如果要接受输入字，则堆栈上有一个或多个A.