Разработка компиляторов

       

Недетерминированные и конечные автоматы


Имеет место следующая теорема: если для некоторого недетерминированного конечного автомата , то для некоторого детерминированного автомата .

Эта теорема доказывается конструктивным образом, т.е. путем указания общего алгоритма построения детерминированного автомата , определяющего тот же язык, что и . Пусть ; тогда мы определим следующим образом:

  • совпадает с множеством состояний автомата
  • для всех , где содержит 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";



Содержание раздела