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


           

У этого автомата множество состояний



Рис. 5.3. 

У этого автомата множество состояний Q = Q1
Q2 , начальное состояние q0= q01, заключительное состояние qf =qf2, а программа включает программы автоматов M1 и M2 и одну новую команду - ?-переход из заключительного состояния M1

в начальное состояние M2, т.е. ? = ?1
?2
{ qf1
q02}. Здесь также очевидно, что всякий путь из q0= q01 в qf =qf2 проходит через ?-переход из qf1 в q02. Поэтому всякое слово, допускаемое M, представляет конкатенацию некоторого слова из LM1} с некоторым словом из LM2}, и любая конкатенация таких слов допускается. Следовательно, НКА M распознает язык Lr =L r1 ? r2}=L r1 Lr2.

Пусть r = r1*. Диаграмма НКА M= <?, Q, q0, {qf}, ? >, распознающего язык Lr=Lr1* = LM1*

представлена на рис. 5.3.


Рис. 5.3.  Диаграмма автомата M, распознающего язык Lr1*

У этого автомата множество состояний Q = Q1
{ q0, qf}, где q0 - это новое начальное состояние, qf - новое (единственное !) заключительное состояние, а программа включает программу автомата M1 и четыре новых команды ?-переходов: ? = ?1
{q0
q01, q0
qf, qf1
q01, qf1
qf}. Очевидно, ?
LM. Для непустого слова w по определению итерации w
Lr1*
для некоторого k
1 слово w можно разбить на k подслов: w=w1w2… wk и все wi
LM1. Для каждого i= 1,… ,k слово wi переводит q01 в qf1. Тогда для слова w в диаграмме M имеется путь



Следовательно, w
LM. Обратно, если некоторое слово переводит q0 в qf, то либо оно есть ? , либо его несет путь, который, перейдя из q0 в q01 и затем пройдя несколько раз по пути из q01 в qf1 и вернувшись из qf1 в q01 по ?-переходу, в конце концов из qf1 по ?-переходу завершается в qf. Поэтому такое слово w
L M1*.

Из теорем 4.2 и 5.1 непосредственно получаем

Следствие 5.1.

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

Это утверждение - один из примеров теорем синтеза: по описанию задания (языка как регулярного выражения) эффективно строится программа (ДКА), его выполняющая.

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