regular-language - 0转PDA的语言与常规语言一致吗？

Question

如果对于其语言中的任何字符串 w，PDA(Pushdown Automaton)最多转动其堆栈的方向 k 次，则称其为 k 转。众所周知，语言 L 是线性的当且仅当被 1 圈 PDA 接受。现在，常规语言真的是 0 转 PDA 接受的语言吗？

Answer 1

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

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

此外，正则语言是 Chomsky classification 中线性语言的子集(右线性或左线性)。