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



             

Автоматы для регулярных языков - часть 2



Рис. 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.

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

Рис. 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 имеется путь

q_0 \stackrel{\varepsilon}{\longrightarrow} q_0^1 \stackrel{w_1}{\longrightarrow}q_f^1 \stackrel{\varepsilon}{\longrightarrow} q_0^1 \stackrel{w_2}{\longrightarrow}q_f^1 \ldots q_0^1 \stackrel{w_k}{\longrightarrow}q_f^1 \stackrel{\varepsilon}{\longrightarrow}q_f

Следовательно, w

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

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

Следствие 5.1.

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

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


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