Разработка компиляторов
Недетерминированные и конечные автоматы
Имеет место следующая теорема: если для некоторого недетерминированного конечного автомата , то для некоторого детерминированного автомата .
Эта теорема доказывается конструктивным образом, т.е. путем указания общего алгоритма построения детерминированного автомата , определяющего тот же язык, что и . Пусть ; тогда мы определим следующим образом:
- совпадает с множеством состояний автомата
- для всех , где содержит p для некоторого
Можно показать, что задает тот же язык, что и . Таким образом, классы языков, задаваемых детерминированными и недетерминированными конечными автоматами, полностью совпадают. Естественно, детерминированные конечные автоматы удобнее, и в дальнейшем мы будем иметь дело только с ними. Следующий набросок программы демонстрирует моделирование конечного автомата (предполагается, что входная лента заканчивается символом end_of_file):
q = q0; c = GetChar(); while (c != eof) { q = move (q, c); c = GetChar(); } if (q is in F) return "yes"; else return "no";
