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

Определение 2.6.1. Конечный автомат называется детерминированным (deterministic), если

1. множество I содержит ровно один элемент;

2. для каждого перехода выполняется равенство |x| = 1;

3. для любого символа и для любого состояния существует не более одного состояния со свойством .

Пример 2.6.2. Конечный автомат из примера 2.1.14 является детерминированным.

Определение 2.6.3. Детерминированный конечный автомат называется полным (complete), если для каждого состояния и для каждого символа найдется такое состояние , что .

Пример 2.6.4. Конечный автомат из примера 2.1.14 эквивалентен полному детерминированному конечному автомату , где Q = {1,2,3}, , I = {1}, F = {1,2},

Замечание 2.6.5. Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения функцию . От функции можно перейти к отношению , положив

2.7. Преобразование конечного автомата к детерминированному виду

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

Доказательство. Без ограничения общности можно предположить, что исходный язык задан конечным автоматом , содержащим только переходы с метками длины единица. Для любых и обозначим

Обозначим через множество всех подмножеств множества Q. Построим искомый полный детерминированный конечный автомат , положив ,

и .

Пример 2.7.2. Пусть . Рассмотрим конечный автомат , где

Если применить конструкцию из доказательства теоремы 2.7.1. и затем удалить состояния, не достижимые из начального состояния, то получится полный детерминированный конечный автомат

где

Упражнение 2.7.3. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.

Упражнение 2.7.4. Найти детерминированный конечный автомат для языка, порождаемого грамматикой

Для практического применения теории конечных автоматов нужны средства, позволяющие выяснять, является ли некоторый формальный язык автоматным. Для получения положительного ответа на такой вопрос могут пригодиться достаточные условия автоматности, для отрицательного ответа - необходимые условия автоматности. В этой лекции рассматриваются наиболее часто используемые условия, касающиеся автоматности формального языка.

В первых двух разделах этой лекции доказываются свойства замкнутости класса всех автоматных языков (относительно итерации, конкатенации, объединения, дополнения, пересечения и т. д.). Эти свойства можно использовать как достаточные условия автоматности. Например, если нужно выяснить, является ли язык L автоматным, и удается представить L в виде , где языки L₁ и L₂ автоматные, то и язык L обязательно является автоматным.

В последних двух разделах этой лекции доказывается так называемая лемма о разрастании (в англоязычной литературе pumping lemma), которая во многих случаях позволяет установить неавтоматность формального языка. К сожалению, эта лемма помогает не всегда, так как дает всего лишь необходимое условие, а не критерий автоматности.