![]() |
|
Главная Промышленная автоматика. состояния определяются с помощью разбиения множества всех достижимых состояний на классы эквивалентности так, что каждый класс содержит неразличимые состояния и выбирается как можно шире. Потом из каждого класса берется один представитель в качестве состояния сокращенного, или приведенного, автомата. Таким способом можно сократить объем автомата М, если М содержит недостижимые состояния пли два и более неразличимых состояний. Мы покажем, что этот приведенный автомат - наименьший из конечных автоматов, распознающих регулярное множество, определяемое первоначальным автоматом М. Определение. Пусть М ~ {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.0018 |