Являются ли DPDA без

В формальном описании автоматов детерминированного пушинга они разрешают перемещения, когда машина может вставлять или помещать символы в стек без чтения символа из ввода. Если эти перемещения недопустимы, а стек может быть изменен только один раз после каждого чтения символа, равны ли полученные автоматы мощности DPDA? $\epsilon$ $\epsilon$

Может быть что-то тривиальное, что мне не хватает в отношении использования powerset качестве вашего нового , позволяющего вам «сжимать» движется в эквивалентный автомат без них, подобно тому, как вы можете сжимать ходы в DFA. Просто кажется, что такое преобразование не так тривиально, как для DFA, и я не уверен, что это даже возможно. $\Gamma$ $\Gamma$ $\epsilon$ $\epsilon$

Так есть ли два эквивалентных по силе? Я просто спрашиваю, потому что все, кажется, предполагают, что DPDA имеют ходы, и мне интересно, почему это предположение существует, так как оно кажется более сложной моделью. $\epsilon$

automata-theory context-free Phylliida
источник

Ладно. Так есть ли причина, по которой мы изучаем только те, которые

ходов?

ϵ

$\epsilon$

Филиллида

Так что я только что понял, что вы действительно можете распознать

. Вы просто начинаете в состоянии принятия, затем, читая первый

, вы помещаете & в стек, а после чтения второго

вы помещаете # в стек. После этого вы записываете

в стек для каждого другого

вы читаете, начиная с

вы прочитали после нажатия # в стек.

L = {a^{2 n} b^{n}}

$L=\{a^{2n}b^n\}$

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

Филиллида

Затем, если вы читаете

, зная, что читаете нечетное число

, вы отклоняете его (находитесь в застрявшем состоянии), в противном случае вы переходите в другое состояние и выталкиваете

из стека. Вы повторяете это для каждого

прочитанного. Если в конце концов при синтаксическом анализе

, # находится на вершине стека вместо

, войдите в состояние принятия. Затем войдите в состояние отклонения, если еще какие-либо символы читаются. В любом случае, отличном от описанного выше, введите состояние отказа. Это работает?

b

$b$

a

$a$

a

$a$

b

$b$

b

$b$

a

$a$

Филиллида

Звучит неплохо.

Клаус Дрегер

Поправь меня, если я ошибаюсь, но я согласен. Я также считаю, что вы можете распознать

с помощью DPDA, который всегда движется прямо на входной ленте (не останавливаясь). Единственная сложная часть - заставить его закончить в конечном состоянии. Принятие DPDA может быть сложно.

{a^{2 n} b^{n}}

$\{ a^{2n}b^{n} \}$

Майкл Вехар

Возможно, я нашел соответствующую информацию в:

Жан-Мишель Отебер, Жан Берстель, Люк Боассон; Языки без контекста и автоматы Pushdown; Справочник по формальным языкам; 1997, стр. 111-174

DPDA без переходов известны как детерминированные автоматы в реальном времени . $\epsilon$

Например, они менее мощные, чем DPDA.

$L = \{ a^n b^p c a^n \mid p,n > 0\} \cup \{ a^nb^pdb^p\mid p,n > 0 \}$

является детерминированным и может быть распознан DPDA, но не может быть распознан любым DPDA в реальном времени .

Что вы можете сделать , это ликвидировать увеличение -переходов: $\epsilon$

Предложение 5.4 : Для любого DPDA можно построить DPDA признать тот же язык, что любая -правило сокращается. $\epsilon$

Марцио де Биаси
источник

Круто, спасибо! Так что это отвечает на первую часть моего вопроса. Вторая часть - почему бы нам не изучить их? Все, кажется, сосредоточены на не в реальном времени, и это кажется странным для меня.

Филиллида

@DanielleEnsign: поискивая, вы можете найти некоторые результаты о RDPDA, например, проблема эквивалентности разрешима . Но я согласен с вами, они не привлекли большого внимания.

Марцио Де Биаси

Являются ли DPDA без

Ответы: