0轉PDA的語言是否與常規語言一致？

一個PDA（Pushdown Automaton）被稱爲k轉，如果對於其語言中的任何字符串w，最多轉動其堆棧的方向k次。另外，衆所周知，如果一圈PDA被接受，語言L是線性的。現在，正規語言是0轉PDA接受的語言，這是真的嗎？0轉PDA的語言是否與常規語言一致？

是，
你可以把有限自動機作爲一種0-turn PDA在堆棧從未使用過。

如果堆棧在自動機的兩個連續描述中分別上升和下降，則稱PDA執行轉彎。並且對於每種常規語言，可以構造一個PDA，其中我們在字符串接受結束時清空PDS。

另外，正則語言是Chomsky classification（右線性或左線性）中線性語言的子集。

2012-12-14 06:09:46

它很好，但反過來呢？我的意思是你如何證明0轉的語言是正常的？可能是這樣的：對於一個給定的pda，其狀態= Q且堆棧符號= G，構造一個狀態爲Q \ times G的dfa，然後dfa通過讀取符號''從（p，X）移動到（q，Y） a'，如果pda從（p，aw，X）移動到（q，w，Y）。 –

是的，你是正確的。有'N'狀態的有限自動化可以模擬爲'2狀態'和'N堆棧符號'的PDA。反過來就是你說的。 –

回答