爲什麼使用下推自動機（PDA）無法定義以下語言？

是否可以爲此語言設計PDA？

我認爲答案是否定的，它只能使用至少一個上下文無關語法來定義。

但是，我不知道爲什麼。我需要一些關於此的討論和解釋。

2014-12-02 NBN

請參閱http://stackoverflow.com/questions/2597124/context-free-language-question-pumping-lemma – ComputerDruid 2014-12-02 23:51:07

@ComputerDruid感謝您的注意。我不知道奧格登的引理。但是，我確實想知道爲什麼不能有這種語言的PDA。我認爲設計一個PDA可能會有點不可能，但我認爲這很難，但仍然有可能。 – NBN 2014-12-03 00:00:22

答案是否定的。其實這種語言既沒有CFG也沒有NPDA。證明可以使用上下文無關語言的抽象引理來建立。

2014-12-28 12:11:03 abbaasi

回答