Алгоритм построения детерминированного КА по НКА

Алгоритм построения детерминированного КА по НКА

Вход: M = (K, VT, d, H, S) - недетерминированный конечный автомат.

Выход: M’ = (K’, VT, d’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М.

Метод:

1.  Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать [A₁A₂...A_n], где A_i Î K.

2.  Отображение d’ определим как d’ ([A₁A₂...A_n], t) = [B₁B₂...B_m], где для каждого 1 £ j £ m d(A_i, t) = B_j   для каких-либо 1 £ i £ n.

3.  Пусть H = {H₁, H₂, ..., H_k}, тогда H’ = [H₁, H₂, ..., H_k].

4.  Пусть S = {S₁, S₂, ..., S_p}, тогда S’ - все состояния из K’, имеющие вид [...S_i...], .S_i Î S для какого-либо 1 £ i £ p.

Замечание: в множестве K’ могут оказаться состояния, которые недостижимы из начального состояния, их можно исключить.

Проиллюстрируем работу алгоритма на примере.

Пусть задан НКА M = ({H, A, B, S}, {0, 1}, d, {H}, {S}), где

   d(H, 1) = B                      d(B, 0) = A

   d(A, 1) = B                       d(A, 1) = S ,

тогда соответствующий детерминированный конечный автомат будет таким:

K’ = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS], [ABS], [HBS], [HABS]}

   d’([A], 1) = [BS]               d’([H], 1) = [B]

   d’([B], 0) = [A]                 d’([HA], 1) = [BS]

   d’([HB], 1) = [B]               d’([HB], 0) = [A]

   d’([HS], 1) = [B]               d’([AB], 1) = [BS]

   d’([AB], 0) = [A]               d’([AS], 1) = [BS]

   d’([BS], 0) = [A]               d’([HAB], 0) = [A]

   d’([HAB], 1) = [BS]           d’([HAS], 1) = [BS]

   d’([ABS], 1) = [BS]           d’([ABS], 0) = [A]

   d’([HBS], 1) = [B]             d’([HBS], 0) = [A]

   d’([HABS], 1) = [BS]         d’([HABS], 0) = [A]

S’ = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]}

Достижимыми состояниями в получившемся КА являются [H], [B], [A] и [BS], поэтому остальные состояния удаляются.

Таким образом (см.рис.3.2), M’ = ({[H], [B], [A], [BS]}, {0, 1}, d’, H, {[BS]}), где

   d’([A], 1) = [BS]               d’([H], 1) = [B]

   d’([B], 0) = [A]                 d’([BS], 0) = [A]

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

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

По конечному автомату часто можно построить автомат с меньшим числом состояний, эквивалентный исходному. Соответствующий процесс называется минимизацией конечного автомата. Вначале выбросим из автомата все состояния, недостижимые из начального. Затем разобьем все состояния КА на классы эквивалентности следующим способом: в первый класс отнесем все конечные состояния, а во второй - все остальные. Назовем  эти  состояния  0-эквивалентными. Теперь построим новое 1-эквивалентное разбиение,  выделив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния. Последовательно строя n+1-эквивалентные состояния по n-эквивалентным, мы будем увеличивать число классов эквивалентности. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпадет с n-эквивалентным. Каждый полученный класс эквивалентности и будет состоянием нового  минимизированного КА, эквивалентного исходному (почему? - упражнение).

Рассмотрим конечный автомат, представленный на рис.3.3а.

Состояния F и G недостижимы (это можно выяснить, например, вычислив транзитивное замыкание отношения "есть переход"). Построим классы n-эквивалентности для оставшихся состояний:

n     Классы

0     (ABC) (DE)

1     (A) (BC) (DE)

2     (A) (BC) (DE)

В результате будет получен конечный автомат, представленный на рис.3.3б.

Рис.3.3. «Избыточный» (a) и минимизированный (б) конечный автомат

Рассмотрим специальный класс операций над языками - регулярные операции.

Множество языков, получаемое из элементарных языков в результате применения конечного числа регулярных операций, - регулярные множества.

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

Определение регулярного множества

Определим над множествами цепочек символов из алфавита V операции конкатенации и итерации следующим образом:

РQ - конкатенация PÎV* и QÎV*: PQ, = {pq | "pÎP, "qÎQ.};

Р* - итерация PÎV*: Р* ⁼ {р* | "pÎP}.

Тогда для алфавита V регулярные множества определяются рекурсивно:

1. Æ — регулярное множество.

2. {l} — регулярное множество.

3. {а} — регулярное множество "aÎV.

4. Если Р и Q, — произвольные регулярные множества, то множества PÈQ, PQ и Р* также являются регулярными множествами.

5. Ничто другое не является регулярным множеством.

Фактически регулярные множества — это множества цепочек символов над заданным алфавитом, построенные определенным образом (с использованием операций объединения, конкатенации и итерации).

Все регулярные языки представляют собой регулярные множества.

Регулярные выражения. Свойства регулярных выражений

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

1. 0 — регулярное выражение, обозначающее Æ.

2. l — регулярное выражение, обозначающее {l}.

3. а — регулярное выражение, обозначающее {a} "aÎV.

4. Если р и q — регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, р* — регулярные выражения, обозначающие регулярные множества PÈQ, PQ и Р* соответственно.

Два регулярных выражения a и b равны, a = b, если они обозначают одно и то же множество.

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

При записи регулярных выражений будут использоваться круглые скобки, как и для обычных арифметических выражений. При отсутствии скобок операции выполняются слева на право с учетом приоритета. Приоритет для операций принят следующий: первой выполняется итерация (высший приоритет), затем конкатенация, потом — объединение множеств (низший приоритет).

Если a, b и g — регулярные выражения, то свойства регулярных выражений можно записать в виде следующих формул:

1. g+aa* = g+a*a = a*

2. a+b = b+a.

3. a+(b+g) = (a+b)+g

4. a(b+g) = ab+ag

5. (b+g)a = ba+ga

6. a(bg) = (ab)g

7. a+a = a

8. a+a* = a*

9. l+a* = a*+l = a*

10. 0* = l

11. 0a = a0 = 0

12. 0+a = a+0 = a

13. la = al = a

14. (a*)* = a*

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

Следует также обратить внимание на то, что среди прочих свойств отсутствует равенство ab = ba, то есть операция конкатенации не обладает свойством коммутативности. Это и не удивительно, поскольку для этой операции важен порядок следования символов.

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

Три способа задания регулярных языков

Три основных способа, с помощью которых можно задавать регулярные языки – это:

·                   регулярные (праволинейные и леволинейные) грамматики,

·                   конечные автоматы (КА) и

·                   регулярные множества (равно как и обозначающие их регулярные выражения).

Регулярные языки в принципе можно определять и другими способами, но именно три указанных способа представляют наибольший интерес.

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

Утверждение 2.1. Язык является регулярным множеством тогда и только тогда, когда он задан леволинейной (праволинейной) грамматикой.

Утверждение 2.2. Язык может быть задан леволинейной (праволинейной) грамматикой тогда и только тогда, когда он является регулярным множеством.

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

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

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

Связь регулярных выражений и регулярных грамматик

Регулярные выражения и регулярные грамматики связаны между собой следующим образом:

·                   для любого регулярного языка, заданного регулярным выражением, можно построить регулярную грамматику, определяющую тот же язык;

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

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

Связь регулярных выражений и конечных автоматов

Регулярные выражения и недетерминированные конечные автоматы связаны между собой следующим образом:

·                   для любого регулярного языка, заданного регулярным выражением, можно построить конечный автомат, определяющий тот же язык;

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

Известен алгоритм, реализующий построение конечного автомата по регулярному выражению [3]. Алгоритм построения регулярного выражения по конечному автомату здесь не представляет интереса, поскольку проще построить грамматику, эквивалентную заданному конечному автомату, а потом уже найти регулярное выражение для заданного грамматикой языка.

Связь регулярных грамматик и конечных автоматов

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

Это очень важное утверждение, поскольку регулярные грамматики используются для определения лексических конструкций языков программирования. Создав автомат на основе известной грамматики, мы получаем распознаватель для лексических конструкций данного языка. Таким образом, удается решить задачу разбора для лексических конструкций языка, заданных произвольной регулярной грамматикой. Обратное утверждение также полезно, поскольку позволяет узнать грамматику, цепочки языка которой допускает заданный автомат.

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

Все языки программирования определяют нотацию записи «слева направо». В той же нотации работают и компиляторы. Поэтому далее рассмотрены алгоритмы для леволинейных грамматик.

Построение конечного автомата на основе леволинейной грамматики

Пусть имеется леволинейная грамматика G(VT,VN,P,S), необходимо построить эквивалентный ей конечный автомат M(Q,V,d,qo,F).

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

Тогда построение конечного автомата M(Q,V,d,qo,F) на основе грамматики G(VT, VN, P, S) выполняется по следующему алгоритму.

Шаг 1. Строим множество состояний автомата Q, Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грамматики G соответствовало одно состояние из множества Q автомата М. Кроме того, во множество состояний автомата добавляется еще одно дополнительное состояние, которое будем обозначать Н. Сохраняя обозначения нетерминальных символов грамматики G, для множества состояний автомата М можно записать:

Q=VNÈ{H}.

Шаг 2. Входным алфавитом автомата М является множество терминальных символов грамматики G: V = VT.

Шаг 3. Просматриваем все множество правил исходной грамматики.

Если встречается правило вида A®tÎP, где AÎVN, tÎVT, то в функцию переходов d(H,t) автомата М добавляем состояние A: AÎd(H,t).

Если встречается правило вида A®BtÎP, где A,BÎVN, tÎVT, то в функцию переходов d(B,t) автомата М добавляем состояние A: AÎd(B,t).

Шаг 4. Начальным состоянием автомата М является состояние Н: qo = Н.

Шаг 5. Множество конечных состояний автомата М состоит из одного состояния. Этим состоянием является состояние, соответствующее целевому символу грамматики G: F = {S}.

На этом построение автомата заканчивается.

Построение леволинейной грамматики на основе конечного автомата

Имеется конечный автомат M(Q, V, d, qo, F), необходимо построить эквивалентную ему леволинейную грамматику G(VT, VN, P, S).

Построение выполняется по следующему алгоритму.

Шаг 1. Множество терминальных символов грамматики G строится из алфавита входных символов автомата М: VT = V.

Шаг 2. Множество нетерминальных символов грамматики G строится на основании множества состояний автомата М таким образом, чтобы каждому состоянию автомата, за исключением начального состояния, соответствовал один нетерминальный символ грамматики: VN = Q\{qo}.

Шаг 3. Просматриваем функцию переходов автомата М для всех возможных состояний из множества Q для всех возможных входных символов из множества V.

Если имеем d(A,t) = Æ, то ничего не выполняем.

Если имеем d(A,t) = {B1,B2,...,Bn}, n >0, где AÎQ, "n³i³0: BiÎQ, tÎV, тогда для всех состояний Вi выполняем следующее:

·                   добавляем правило Bi®t во множество Р правил грамматики G, если А = qo;

·                   добавляем правило Bi®At во множество Р правил грамматики G, если A ¹ qo.

Шаг 4. Если множество конечных состояний F автомата М содержит только одно состояние F = {F0}, то целевым символом S грамматики G становится символ множества VN, соответствующий этому состоянию: S = Fo; иначе, если множество конечных состояний F автомата М содержит более одного состояния F = {F1, F2,...,Fn}, n>1, тогда во множество нетерминальных символов VN грамматики G добавляется новый нетерминальный символ S: VN = VNÈ{S}, а во множество правил Р грамматики G добавляются правила: S®F1 | F2 | ... | Fn.

На этом построение грамматики заканчивается.

Пример построения конечного автомата на основе заданной грамматики

Рассмотрим грамматику G({"a", "(", "*", ")", "{", "}"}, {S.C.K}, Р, S) (символы а, (, *, ), {, } из множества терминальных символов грамматики взяты в кавычки, чтобы выделить их среди фигурных скобок, обозначающих само множество):

Р:      S ® С*) | К}

С ® (* | Са | С{ | С} | С( | С* | С)

К ®. { | Ка | К( | К* | К) | К{

Это леволинейная регулярная грамматика. Она описывает множество комментариев языка Паскаль. Как было показано выше, ее можно преобразовать к автоматному виду.

После преобразования получим леволинейную автоматную грамматику следующего вида: G'({"a", "(", "*",.")", "{", "}"}, {S, D, C, E, K}, P', S):

Р':     S ® E) | К}

D ®C*

С ® D* I Са | C{ | C} | C( | C* | C)

E ® (

К ® { | Ка | K( | K* | K) | K{

Построим конечный автомат M(Q,V,d,qo,F), эквивалентный указанной грамматике.

Шаг 1. Построим множество состояний автомата: Q = VNÈ{H}= {S, E, C, D, K, H}.

Шаг 2. В качестве алфавита входных символов автомата берем множество терминальных символов грамматики. Получаем: V = {"а", "(", "*", ")", "{", "}"}.

Шаг 3. Рассматриваем множество правил грамматики.

Для правил S ® Е) | К} имеем d(Е,")") = {S}; d(K,"}") = {S}.

Для правила Е ® С* имеем d(С,"*") = {Е}.

Для правил С ® D* | Са | С{ | С} | С( | С* | С) имеем d(D,"*") = {С}; d(С,"а") = {С};  d(С,"{") ⁼ {С}; d(С, "}") = {С}; d(С,"(") = {С}; d(С, “*”) = {Е.С}; d(С, ")") = {С}.

Для правила D ® ( имеем d(Н, "(") = {D}.

Для правил К ® { | Ка | К( | К* | К) | К{ имеем d(Н, "{") = {К}; d(К, "а") = {К}; d(К, “(") = {К}; d(К,"*") = {К}; d(К, ")") = {К}; d(К, "{") = {К}.

Шаг 4. Начальным состоянием автомата является состояние qo = Н.

Шаг 5. Множеством конечных состояний автомата является множество F = {S}.

Выполнение алгоритма закончено.

В итоге получаем автомат M({S.E,C,D,K,H}, {"а", "(", "*", ")",."{", "}"}. d, Н, {S}) с функцией переходов:

d(Н, "{") ⁼ {K}     d(H, "(") = {D}              d(К, "а") = {К}              d(К, "(") = {К}

d(К, "*") = {К}       d(К, ")") = {К}                d(К, "{“) = {К}                d(К, ")") = {S}

d(D, "*") = {С}      d(С, "а") = {С}              d(С, "{") = {С}               d(C, "}") = {С}

d(С, "(") = {С}      d(С, "*") = {Е, С} d(С, ")") = (С)               d(Е, “)”) = {S}

Граф переходов этого автомата изображен на рис. 4.1.

a,(,*,),{,}

Рис. 4.1. Недетерминированный КА для языка комментариев в Borland Pascal

Это недетерминированный конечный автомат, поскольку существует состояние, в котором множество, получаемое с помощью функции переходов по одному и тому же символу, имеет более одного следующего состояния. Это состояние С и функция d(С,"*") = {Е,С}.

Моделировать поведение недетерминированного КА - непростая задача, поэтому можно построить эквивалентный ему детерминированный КА. Полученный таким путем КА можно затем минимизировать.

В результате всех преобразований получаем детерминированный конечный автомат М'({S.E,С,D, К,Н}, {"а", "(", "*", ")", "{", "}"} .d', H, {S}) с функцией переходов:

d'(Н, "{") = {К}      d'(Н, “(") = {D}     d'(К, "а") = {К}     d'(К, "(") = {К}      d'(К, "*") = {К}     d'(К, ")") = {К}

d'(К, "{") = {К}      d'(К, "}") = {S)      d'(D, "*") = {С}     d'(С, "а") = {С}    d'(С, “{“) = {С}    d'(С, "}") = {С}

d'(С, "(") = {С}     d'(С, ")") = {С}     d'(С, "*") = {Е}     d'(Е, “а") = {С}     d'(E, “{“) = {С}    d'(Е, "}") = {С}

d'(Е, "(") = {С}     d'(Е, "*") = {Е}     d'(Е, ")") = {S}

Граф переходов этого автомата изображен на рис. 4.2.

а, (,),{,}

Рис. 4.2. Детерминированный КА для языка комментариев в Borland Pascal

На основании этого автомата можно легко построить распознаватель. В данном случае мы можем получить распознаватель для двух типов комментариев языка Программирования Borland Pascal, если учесть, что а может означать любой алфавитно-цифровой символ, кроме символов (, *, ), {, }.

Свойства регулярных языков

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

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

Регулярные множества (и однозначно связанные с ними регулярные языки) замкнуты относительно многих операций, которые применимы к цепочкам символов.

Например, регулярные языки замкнуты относительно следующих операций:

·                   пересечения;

·                   объединения;

·                   дополнения;

·                   итерации;

·                   конкатенации;

·                   гомоморфизма (изменения имен символов и подстановки цепочек вместо символов).

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

Регулярные языки представляют собой очень удобный тип языков. Для них разрешимы многие проблемы, неразрешимые для других типов языков.

Например, доказано, что разрешимыми являются следующие проблемы.

·                   Проблема эквивалентности. Даны два регулярных языка L1(V) и L2(V). Необходимо проверить, являются ли эти два языка эквивалентными.

·                   Проблема принадлежности цепочки языку. Дан регулярный язык L(V) и цепочка символов aÎV*. Необходимо проверить, принадлежит ли цепочка данному языку.

·                   Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, то есть найти хотя бы одну цепочку a¹l, такую что aÎL(V).

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

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