Главная Промышленная автоматика.

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

Определение. Пусть М ~ {Q, 2, 6, q, Р) -конечный автомат, а и 3 - различные его состояния. Будем говорить, что цепочка х2* различает состояния q и q, если {qi, х)[~* (q,e), (2) Н* (4» ) н одно из состояний q<t и q принадлежит/, а другое нет. Будем говорить, что q и q k-неразличимы, п писать (7i = 92, сли не существует такой цепочки л:, различающей 9i н (?2, у которой Будем говорить, что состояния q

и неразличимы, и писать qq, если они /г-неразличимы для любого ft 0.

Состояние qQ называется недостижимым, если не существует такой входной цепочки х, что {д, х)\-* {q,e).

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

Пример 2.14. Рассмотрим конечный автомат М, диаграмма которого показана на рис. 2.5.

тчало


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

Чтобы сократить Af, заметим сначала, что состояния F п G недостижимы из начального состояния А, так что пх можно устранить. Позднее, применяя алгоритм 2.2, мы увидим, что классами эквивалентности отношения = будут {А}, {В, D\ и {С,Е}. Тогда, взяв представителями этих множеств состояния

р, q Я Г соответственно, можно получить конечный автомат, изображенный на рис. 2.6, который является приведенным автоматом, эквивалентным М. □

начт


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

Лемма 2.11. Пусть М = [Q, X, 6, q, F)~конечный автомшп с п состояниями. Состояния q и q неразличимы тогда и только тогда, когда они (п - 2)-неразличимы.

Доказательство. Необходимость условия тривиальна. Достаточность тривиальна в тех случаях, когда F имеет О или п элементов. Поэтому рассмотрим случай, когда число элементов множества F отлично от О или п.

Покажем, что

Для этого заметим, что для любых состояний q и q

(1) q=q тогда и только тогда, когда и q,, оба либо принадлежат, либо не принадлежат F,

(2) qq тогда и только тогда, когда q=- q. и b(qj,a) b(q.,a) для всех й2.

Отношение грубейшее; оно разбивает Q на два класса: F и Q -f. Если +=, то отношение тоньше, чем

т. е. в нем по крайней мере на один класс эквивалентности больше, чем в Так как каждое из множеств F и Q-F содержит не более п-1 элементов, можно получить не более п -2 последовательных утончений отношения =*. Если =*"i=* для некоторого к, то в силу (2) + i = ... . Таким образом,

=-это первое из отношений для кшорых = ==*, □

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

Алгоритм 2.2, Построение канонического конечного автомата.

Вход. Конечный автомат М = (Q, 2, 6, о» )-

Выход, Эквивалентный приведенный конечный автомат М.



Метод.

Шаг 1: Применив к диаграмме автомата М алгоритм 0.3, найти состояния, недостижимые из q. Устранить все недостижимые состояния.

Шаг 2: Строить отношения эквивалентности .,., как

описано в лемме 2.И, до тех пор, пока два из них не совпадут: =к Взять В качестве = отношение

Шаг 3: Построить конечный автомат М = {Q, 2, б, q, где

(а) Q -множество классов эквивалентности отношения =е (обозначим через [я] класс эквивалентности отношения , содержащий состояние я),

(б) б([я], а)-И, если 6{p,a)=q,

(в) это [(/о].

(г) F={[q]\qf}. □

Можно непосредственно показать, что шаг 3(6) непротиворечив, т. е. какой элемент класса [р] ни взять, для б ([я], а) будет один и тот же класс. Доказательство равенства L (Л1) -L{M) тоже просто и оставляется в качестве упражнения. Докажем теперь, что автомат с меньшим числом состояний, чем у ЛГ, не может допускать L{M).

Теорема 2.6. Автомат. М, который строится алгоритмом 2.2, имеет наименьшее число состояний среди всех конечных автоматов, допускающих язык L(M).

Доказательство. Предположим, что М" имеет меньше состояний, чем М, и что 1{M") = L(M). В силу шага 1 алгоритма 2.2 каждое состояние автомата М достижимо. Так как


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

М" имеет меньше состояний, то найдутся цепочки w я х, переводящие состояние 9о в разные состояния, а q" (начальное состояние автомата Л1") -в одно и то же: (f?o, oi) Нм.. (/, е) и (о. Нл1"(?)- Следовательно, w \\ х переводят автомат М в раз-

личимые состояния, скажем риг. Это значит, что существует такая цепочка у, что точно одна из цепочек wy и ху принадлежит L{M). Но wy и ху должны переводить М" в одно и то же состояние S, для которого [q, y)\-M{s,e). Таким образом, точно одна из цепочек wy и ху не может принадлежать L{M"), а это противоречит предположению о том, что L{M")=L(M). □

Таблица 2.3

Пример 2.15. Найдем приведенный конечный автомат, эквивалентный автомату М, диаграмма которого показана на рис. 2.7. Отношения для /е О имеют следующие классы эквивалентности:

Классы отношения Классы отношения = Классы отношения

{A,F\, \B,C,D,E} {A,F\, {В,Е}, {CD} {A,F\, {B,E}, {CD}

Так как =2=i=\ то = = Приведенным автоматом Мбудет автомат ({\А], [С]}, {а,Ь}, 6, Л, {[Л]}), где функция б

определяется табл. 2.3. Здесь мы выбрали [А] для представления класса {A,F}, [Sj -для представления {В, Е} и [CJ-для {С, D}. Q

2.3.2. Лемма о разрастании для регулярных множеств

Теперь мы хотим получить характеристику регулярных множеств, которая будет полезна для доказательства того, что некоторые языки не являются регулярными. Следующую теорему назовем леммой о „разрастании", потому что она в сущности говорит о том, что если даны регулярное множество и достаточно длинная цепочка в нем, то в этой цепочке можно найти непустую подцепочку, которую мол<по повторить сколько угодно раз (т. е. она „разрастается"), и все полученные таким образом „новые" цепочки будут принадлежать тому же регулярному множеству. С помощью этой леммы часто приводят к противоречию предположение о том, что некоторое множество регулярно.



Теорема 2.7. Лемма о разрастании для регулярных множеств.

Пусть L-регулярное множество. Существует такая константа р, что если wL и то цепочку w можно записать в виде

xyz, где 0<\у\р и xyzL для всех iO.

Доказательство. Пусть М = (Q, 2, б, q,, f) - конечный автомат с п состояниями и L{M) = L. Пусть р = п. Если wL и рассмотрим последовательность конфигураций, кото-

рую проходит автомат М, допуска-я цепочку w. Так как в этой последовательности по крайней мере 1 конфигураций, то среди первых rt+l конфигураций найдутся две с одинаковыми состояниями. Поэтому должна быть такая последовательность тактов, что

[q,. xyz) Ь* (Яг, уг) (<7,. г) [-*(q,, е)

для некоторого q и 0</г<«. Отсюда 0<у«. Но тогда для любого i > О автомат может проделать последовательность тактов

{Яохуг) \-*{q,,yz)

\ЧЯиУ-)

\-*(Я.,е)

Так как цепочка w=xyz принадлежит L, то и xyzE для всех i>l. Случай / - О исследуется аналогично. □

Пример 2.16. С помощью леммы о разрастании докажем, что язык L -{0"l"Jrtl} не является регулярным множеством. Допустим, что L регулярен. Тогда для достаточно большого п цепочку 0"1" можно записать в виде хуг, пртем уфе и xyzL для всех tO. Если уО или у£\, то xzxyzL. Если УОА, то xyyzL. Полученное противоречие доказывает, что язык Е не может быть регулярным. □

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

Множество Л называется замкнутым относительно ft-местной операции 9, если 9 [а, а, ..., а) € всегда, когда а,- А для всех Например, множество целых чисел замкнуто

относительно операции сложения.

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

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

Теорема 2.8. Для любого алфавита Б класс регулярных множеств содержаиихся в 2*, является булевой алгеброй множеств:

Доказательство. Докажем замкнутость относительно дополнения. Замкнутость относительно объединения мы уже имеем, а замкнутость относительно пересечения будет следовать из теоретико-множественного закона А[\В = А{}В (упр. 0.1.4). Пусть M = (Q, Д, б, q, /) -конечный автомат, у которого Д sX. Легко показать, что каждое регулярное множество Ls2* допускается некоторым таким автоматом. Тогда конечный автомат M = (Q, Д, б, q, Q-F) допускает A*-/. (УИ), Заметим, что здесь использован тот факт, что автомат М полностью определен. Далее, дополнение L (М) относительно 2* можно представить в виде/Г(Л!)-1 (М) и 2* (2-Д) 2*. Так как множество 2* (2-Д)2* регулярно, то регулярность множества L (М) следует нз замкнутости регулярных множеств относительно объединения. □

Теорема 2.9. Класс регулярных множеств замкнут относительно обращения.

Доказательство. Пусть A1(Q, 2, б, i?,,, f) -конечный автомат, определяющий регулярное множество L. Чтобы определить Е, „запустим М в обратном направлении". Иными словами, возьмем недетерминированный конечный автомат М - (QuW 6, qi, F), где Р = Ы. ecлиeL, и F{q,,qo}, если еЕ. Функцию б определим так:

{\) 6{qo, а) содержит q, если b(q,a)F. (2) б (q, а) для всех Q и л € 2 содержит (7, если 6{q, a) = q.

Легко показать, что (q, ну) Км (?» ) Для qF тогда и только тогда, когда (ql, ш)Нм(7о. Таким образом, Е(М) {Е{М))Е, □

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0036