Может ли детерминированный конечный акцептор начинаться в конце строки и двигаться к началу?

Question

Может ли детерминированный конечный акцептор начинаться в конце строки и двигаться к началу?

Если так, то как это нарисовано в виде графика? что бы вы назвали своим начальным состоянием? и вы бы нарисовали график как движущийся справа налево?

0

automata dfa deterministic states

Источник

user1467202 07 сен '13 в 20:15

1 ответ

Решение

Другие вопросы по тегам automata dfa deterministic states

user2713238 10 сен '13 в 17:35 2013-09-10 17:35 · Accepted Answer · 2013-09-10 17:35

Поскольку вы имеете дело с детерминированными конечными автоматами, ответ - нет.

Основная проблема заключается в том, что у вас может быть два перехода (p, a, r) и (q, a, r), ведущих к одному и тому же состоянию r, но с p, отличным от q. Тогда, если вы начнете с r и попытаетесь прочитать букву a назад, вы должны оказаться в p или в q?