regular-language - Do the languages of 0-turn PDA's coincide with the regular languages?

Question

A PDA (Pushdown Automaton) is said to be k-turn if, for any string w in its language, turn the direction of its stack at most for k times. Also it is well-known that the language L is linear iff accepted by a 1-turn PDA. Now, is it true that the regular languages are the languages which are accepted by a 0-turn PDA?

Answer 1

是的，
您可以将有限自动机视为一种 0-turn PDA从不使用堆栈的自动机。

如果堆栈在自动机的两个连续描述中分别上升和下降，则称 PDA 执行转弯。并且对于每种正则语言 aPDA都可以构造，我们PDS在字符串接受结束时清空。

此外，正则语言是乔姆斯基分类中线性语言的子集（右线性或左线性）。