Языки КПК с 0 поворотами совпадают с обычными языками?
PDA ( Pushdown Automaton) называется k- витком, если для какой-либо строки w на его языке, повернуть направление своего стека максимум на k раз. Также хорошо известно, что язык L является линейным, если он принимается однооборотным КПК. Теперь, правда ли, что обычные языки - это языки, которые принимаются КПК с 0 поворотами?
1 ответ
Да
Вы можете думать, что конечные автоматы как вид 0-turn PDA в котором стек никогда не используется.
Говорят, что КПК выполняет поворот, если стек идет вверх и вниз соответственно в двух последовательных описаниях автоматов. И для каждого регулярного языка PDA может быть построен, в котором мы опорожняем PDS в конце принятия строки.
Кроме того, Регулярный язык является подмножеством линейных языков в классификации Хомского (правая или левая).