Меня смущает реализация языка автоматом. Переходит ли автомат сразу в следующее состояние, если есть ɛ-переход? Предположим, у меня есть автомат, состоящий из трех состояний a, b и c (где a — начальное состояние, а c — принимающее состояние) с алфавитом {0,1}. Как работает следующее?
a----ɛ--->(b----0---->a)
(b----1---->c)
Принимается ли строка "1"? Что, если бы у нас было
a---1--->b----ɛ--->c
? Будет ли принята строка «1»?
Переходит ли автомат сразу в следующее состояние, если есть ɛ-переход?
Грубо говоря, да. ɛ-переход (в недетерминированном конечном автомате, или сокращенно NFA) переход, который не связан с потреблением какого-либо символа (в данном случае 0 или 1). Как только вы это поймете, легко (в данном случае) вывести детерминированные конечные автоматы (или DFA , для краткости), которые эквивалентны вашим NFA и определяют языки, которые описываются последними.
Предположим, у меня есть автомат [...] Принимается ли строка «1»?
да. Вот более красивая диаграмма (любезно предоставленная LaTeX и tikz) вашего первого NFA:
Эквивалентный DFA будет:
Как только вы это сделаете, легко увидеть, что язык, принятый этим NFA, представляет собой набор строк, которые
0,1.Строка "1", поскольку она начинается с нуля 0 и заканчивается единицей 1, действительно принимается.
Что, если бы у нас было [...]? Будет ли принята строка «1»?
да. Вот более красивая диаграмма вашего второго NFA:
Эквивалентный DFA будет:
На самом деле, легко увидеть, что «1» — единственная допустимая строка здесь.
