Теория языков программирования методов трансляции (стр. 11 )

Рис. 3.2. Пример детерминированного графа

Для дальнейшего анализа нам потребуется определение детерминированного автомата.

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

Пусть М = (Q, S, d, q0, F) – недетерминированный конечный автомат. Назовём автомат М детерминированным, если множество d(q, а) содержит не более одного состояния для любых qÎQ и аÎS. Если d(q, а) всегда содержит точно одно состояние, то автомат М назовём полностью определённым.

Рис. 3.3. Пример недетерминированного графа

Таким образом, наш пример – полностью определённый детерминированный конечный автомат, и в дальнейшем под конечным автоматом мы будем подразумевать полностью определённый конечный автомат.

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

Теорема.

Если L=L(M) для некоторого недетерминированного конечного автомата, то L=L(M') для некоторого конечного автомата М'.

Пусть М = (Q, S, d, q0, F). Построим автомат М' = (Q', S, d', q0', F') следующим образом:

1)  Q' = P (Q), т. е. состояниями автомата М' является множество состояний автомата М;

2)  q0'={q0};

3)  F' состоит из всех таких подмножеств S множества Q, что SÇF¹Æ;

4)  d(S, а) = S' для всех SÍQ, где S'={p | d(q, а) содержит р для некоторого qÎS}.

Пример.

Построим конечный автомат М' = (Q,{1, 2, 3}, d', {q0}, F), допускающий язык L(M).

Так как М имеет 5 состояний, то в общем случае М' должен иметь 32 состояния. Однако, не все они достижимы из начального состояния. Состояние р называется достижимым, если существует такая цепочка w, что (q0, w)⊢∗(р, е), где q0 - начальное состояние. Мы будем строить только достижимые состояния (табл. 3.3).

Таблица 3.3 - Достижимые состояния автомата

Состояние	Вход
1	2	3
А = {q0}	В	С	D
В = {q0, q1}	Е	F	G
С = {q0, q2}	F	H	I
D = {q0, q3}	G	I	J
E = {q0, q1, qf}	E	F	G
F = {q0, q1, q2}	K	K	L
G = {q0, q1, q3}	M	L	M
Н = {q0, q2, qf}	F	H	I
I = {q0, q2, q3}	L	N	N
J = {q0, q3, qf}	G	I	J
К = {q0, q1, q2, qf}	К	К	L
L= {q0, q1, q2,q3}	Р	Р	Р
М = {q0, q1, q3, qf}	М	L	М
N = {q0, q2, q3, qf}	L	N	N
Р = {q0, q1,q2, q3, qf}	Р	Р	Р

Начнём с замечания, что состояние {q0} достижимо. d' ({q0}, а) = {q0, qа} для а = 1, 2, 3. Рассмотрим состояние {q0, q1}. Имеем d' ({q0, q1},1) = {q0, q1, qf}. Продолжая, по данной схеме, получаем, что множество состояний автомата М (М¢) достижимо тогда и только тогда, когда

1)  оно содержит q0 и

2)  если оно содержит qf, то содержит также и q1, q2 или q3.

Начальным состоянием автомата М является А, а множество заключительных состояний - {Е, Н, J, К, М, N, Р}.

3.8.  Конечные автоматы и регулярные множества

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

Лемма. Если L=L(M) для некоторого конечного автомата, то L=L(G) для некоторой праволинейной грамматики.

Лемма. Пусть S - конечный алфавит, тогда множества (1) Æ, (2) {е} и {a} для всех аÎ S являются конечно-автоматными языками.

Лемма. Пусть L1 = L(M1) и L2 = L(M2) для конечных автоматов M1 и M2. Множества L1ÈL2, L1 L2 и L1* являются конечно-автоматными языками.

Заключительная теорема.

Язык допускается конечным автоматом тогда и только тогда, когда он является регулярным множеством. Таким образом утверждения

1)  L – регулярное множество;

2)  L – праволинейный язык;

3)  L – конечно-автоматный язык

эквивалентны.

3.9.  Минимизация конечных автоматов

Цель. Показать, что для каждого регулярного множества однозначно находится конечный автомат с минимальным числом состояний.

По данному конечному автомату М можно найти наименьший эквивалентный ему конечный автомат, исключив все недостижимые состояния и затем склеив лишнее состояние. Лишнее состояние определяется с помощью разбиения множества всех состояний на классы эквивалентности так, что каждый класс содержит неразличимые состояния и выбирается как можно шире. Потом из каждого класса берётся один представитель в качестве состояния сокращенного (или приведённого) автомата.

Таким образом можно сократить объём автомата М, если М содержит недостижимые состояния или два или более неразличимые состояния. Полученный автомат будет наименьший из конечных автоматов, распознающий регулярное множество, определяемое первоначальным автоматом М.

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

Пусть М = (Q, S, d, q0, F) конечный автомат, а q1 и q2 два его различные состояния. Будем говорить, что цепочка хÎS* различает состояния q1 и q2, если (q1, х)⊢∗(q3, е), (q2, х)⊢∗(q4 ,е) и одно из состояний q3 и q4 принадлежит F. Будем говорить, что q1 и q2 k- неразличимы, и писать q1q2, если не существует такой цепочки х, различающей q1 и q2, у которой |x|£k. Будем говорить, что состояния q1 и q2, неразличимы и писать q1≡q2, если они k – неразличимы для любого k³0.

Состояние qÎQ называется недостижимым, если не существует такой входной цепочки х, что (q0, х)⊢∗(q, е).

Автомат М называется приведенным, если в Q нет недостижимых состояний и нет двух неразличимых состояний.

Пример. Рассмотрим конечный автомат М с диаграммой (рис. 3.4).

Рис. 3.4. Диаграмма автомата М

Чтобы сократить М, заметим сначала, что состояния F и G недостижимы из начального состояния А, так что их можно устранить. Пока качественно, а позже строго мы установим, что классами эквивалентности отношений являются {A}, {B, D} и {C, E}. Тогда, взяв представителями этих множеств p, q и r, можно получить конечный автомат вида (рис. 3.5).

Рис. 3.5. Приведенный конечный автомат

Перед тем, как построить алгоритм канонического конечного автомата, введём лемму:

Лемма.

Пусть М = (Q, S, d, q0, F) конечный автомат с n состояниями. Состояния q1 и q2 неразличимы тогда и только тогда, когда они (n-2) – неразличимы, т. е. если два состояния можно различить, то их можно различить с помощью входной цепочки, длина которой меньше числа состояний автомата.

Алгоритм построения канонического конечного автомата.

Вход.

Конечный автомат М = (Q, S, d, q0, F).