Введение в схемы, автоматы и алгоритмы



             

Детерминированные конечные автоматы (ДКА) и автоматные языки - часть 3


L_A= \{ w\ |\ A \text{ распознает } \ w\}

Язык называется конечно автоматным, если он распознается некоторым ДКА.

Из этого определения, в частности, следует, что ?

LA
q0
F. Один и тот же язык может распознаваться разными автоматами.

Определение 4.7.

Автоматы A и B называются эквивалентными, если совпадают распознаваемые ими языки, т.е. LA = LB.

Определение распознавания слова и языка можно легко перевести на язык диаграмм.

Лемма 4.3. Автомат A распознает (допускает, принимает) слово w, если для некоторого q

F в диаграмме DA имеется путь из q0 в q, который несет слово w, т.е. w переводит q0 в заключительное состояние q.

Доказательство можно провести индукцией по длине слова w (см. задачу 4.3).

Tаким образом, язык LA, распознаваемый автоматом A, состоит из всех слов, которые переводят в его диаграмме DA начальное состояние q0 в заключительные состояния из F.

Наша цель теперь состоит в изучении класса конечно автоматных языков.

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




Содержание  Назад  Вперед