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

Question

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

Answer 1

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

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

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