Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика»

Приводимое доказательство конструктивно – излагаются алгоритмы построения соответствующих автоматов. Пусть L₁ и L₂ – регулярные языки, распознаваемые конечными автоматами К¹={Q¹, A, q¹₀, g¹, F¹} и К²={Q², A, q²₀, g², F²} соответственно; считаем, что Q¹={q¹₀, q¹₁, q¹₂, ..., q¹_f} и Q²={q²₀, q²₁, q²₂, ..., q²_h}. Автомат К^={Q, A, q₀, g, F^}, распознающий язык L₁L₂, строим следующим образом. Полагаем Q=Q¹хQ²; каждое состояние конструируемого автомата содержит две компоненты, левую и правую. Начальным состоянием нового автомата считаем (q¹₀,q²₀), а функцию переходов g определяем следующим образом:

Очевидно, по первой компоненте автомат К^ моделирует действия автомата К¹, а по второй компоненте – действия автомата К². Входное слово  принадлежит объединению языков L₁ и L₂ тогда и только тогда, когда после его обработки автомат К^ окажется в состоянии, у которого либо первая компонента принадлежит совокупности F¹, либо вторая компонента принадлежит совокупности F².Таким образом, следует положить:

Все компоненты автомата К^ определены, его построение закончено.

Автомат К^={Q, A, q₀, g, F^}, распознающий язык L₁L₂, отличается от К^ только последней своей компонентой. Следует положить

F^=F¹хF².

Пусть К={Q, A, q₀, g, F} – конечный автомат, распознающий язык L. Произвольное слово  из А* принадлежит языку L^с=А*\L тогда и только тогда, когда после его обработки автомат К оказывается в состоянии, не принадлежащем F. Поэтому автоматом, распознающим язык L^с, является конечный автомат К^с={Q, A, q₀, g, Q\F}. Образно говоря, для того, чтобы получить конечный автомат, распознающий дополнение регулярного языка, надо в автомате, распознающем исходный язык, поменять местами «хорошие» и «плохие» состояния.

Теорема доказана.

На рис. 2.14 представлены два конечных автомата, распознающих языки L₁ и L₂. На рис. 2.15 и 2.16 изображены автоматы, распознающие языки L₁L₂ и L₁L₂ соответственно.

На рис. 2.17 представлен автомат, распознающий язык L₃, представляющий собой дополнение к языку L₂. На рис. 2.18 изображен автомат, распознающий разность языков L₁ и L₂ (или пересечение языков L₁ и L₃).

Заметим, что часто автоматы, распознающие объединение и пересечение языков, строятся существенно проще. Это связано с тем, что некоторые состояния из множества состояний Q=Q¹хQ² могут быть недостижимыми. Рассмотрим следующий пример. Пусть требуется построить автомат, распознающий объединение языков L₁ и L₂; автоматы K₁ и K₂, распознающие эти языки, изображены на рис. 2.19.

Диаграмму переходов автомата K^ (рис. 2.20), распознающего язык L₁L₂, строим следующим образом. Вводим вершину, соответствующую начальному состоянию (q₀¹,q₀²). По букве a автомат K₁ из состояния q₀¹ переходит в состояние q₁¹, а автомат K₂ – из q₀² в q₁². Следовательно, автомат K^ из состояния (q₀¹,q₀²) перейдет в состояние (q₁¹,q₁²). Добавим в диаграмму соответствующую вершину и ведущую в нее дугу. Т.к. по букве b автомат K₁ переходит из q₀¹ в q₂¹, а автомат K₂ – из q₀² в q₂², то автомат K^ из состояния (q₀¹,q₀²) перейдет в состояние (q₂¹,q₂²). Соответствующая вершина и дуга добавляются в диаграмму. Рассмотрим вершину (q₂¹,q₂²). По букве a автомат K₁ из q₂¹ переходит в q₁¹, а автомат K₂ – из q₂² в q₁², следовательно; автомат K^ из состояния (q₂¹,q₂²) перейдет в состояние (q₁¹,q₁²), которое уже присутствует на диаграмме. Поэтому в диаграмму добавляется только соответствующая дуга. По букве b автомат K₁ остается в состоянии q₂¹, а автомат K₂ переходит из q₂² в q₀², поэтому автомат K^ по букве b из состояния (q₂¹,q₂²) переходит в состояние (q₂¹,q₀²). В диаграмму добавляются вершина (q₂¹,q₀²) и ведущая в нее дуга. Рассматривая далее вершины (q₁¹,q₁²) и (q₂¹,q₀²), мы обнаружим, что новых вершин не возникает, в диаграмму добавляются лишь дуги, ведущие в уже существующие вершины. «Хорошими» будут являться состояния (q₂¹,q₀²) и (q₂¹,q₂²).

Точно так же строится диаграмма конечного автомата K^, распознающего язык L₁L₂ (рис. 2.21). Автомат K^ отличается от автомата K^ только множеством «хороших» состояний.

Сейчас приведем пример языка, не являющегося регулярным. Пусть х^f, здесь х – произвольная буква рассматриваемого алфавита, обозначает слово, состоящее из буквы х, повторенной f раз, f{1, 2, 3,...}. Запись х^fу^h, где х и у – произвольные буквы алфавита, f{1, 2, 3,...} и h{1, 2, 3,...}, обозначает результат приписывания справа к слову х^f слова у^h. Через L^a-b обозначим бесконечный язык, каждое слово которого имеет вид aⁿbⁿ, т.е. в слове, принадлежащем языку, сначала n раз повторяется буква а, затем такое же число раз повторяется буква b, где n=1, 2, 3,....

Доказательство проводим методом от противного. Пусть данный язык регулярен. Тогда существует распознающий L^a-b конечный автомат К^a-b, число состояний этого автомата обозначим w. Далее через q^z условно обозначим состояние, в котором оказывается автомат К^a-b после того, как он, начиная от своего начального состояния q₀, обработал z букв а подряд, z=1, 2, 3,.... Учитывая, что общее число состояний К^a-b равно w, делаем вывод, что среди состояний, обозначаемых q¹, q², ... , q^w+1, имеется по меньшей мере одно с двумя обозначениями. Пусть qⁱ и q^j, здесь ij, – два обозначения некоторого состояния q_k. Так как слова aⁱbⁱ и a^jb^j принадлежат языку L^a-b, то как слово bⁱ, так и слово b^j переводит автомат К^a-b из состояния q_k, в которое он попадает в результате обработки из начального состояния слова aⁱ или слова a^j, в состояние из множества F. Но тогда процесс работы данного автомата над не принадлежащим языку L^a-b словом =aⁱb^j протекает следующим образом: обработав, начиная от состояния q₀ начальную часть aⁱ слова , автомат оказывается в состоянии q_k; далее, обработав, начиная от состояния q_k заключительную часть b^j входного слова , автомат оказывается в «хорошем» состоянии. Таким образом, слово  принадлежит языку, распознаваемому автоматом К^a-b. Полученное противоречие означает справедливость сформулированной теоремы.

Как отмечалось выше, требуемая информация об обработанной части входного слова «помнится» состояниями автомата. Так как число состояний конечно, то память конечного автомата является ограниченной, не достаточной для запоминания сколь угодно большого числа букв a, прошедших перед появлением на входе первой буквы b.

Через L^_,, где , ,  – фиксированные слова алфавита А={a, b, c}, обозначим язык, состоящий из слов вида  ⁱ, здесь  ⁱ обозначает повторенное i раз слово , i=0, 1, 2, ... (слово  ⁰ считаем по определению пустым). Рассмотрим в качестве примера язык L^abc_bca,cab (здесь =bca, =abc, =cab), данный язык регулярен, диаграмма соответствующего конечного автомата представлена на рис. 2.22. В результате обработки начальной части bca слова  ⁱ автомат из начального состояния q₀ переходит в состояние q₃; далее, обрабатывая подслово , автомат реализует цикл q₃, q₄, q₅, q₃ (этот цикл выполняется i раз); заключительная часть  обеспечивает переход автомата из состояния q₃ в «хорошее» состояние q₈. Отметим, что, следуя указанному принципу при построении диаграммы конечного автомата для языка L^abc_bca,асb, мы встретимся с осложнением: из состояния q₃ по букве а следует идти в q₄, если этой буквой начинается очередное подслово , и в q₆, если этой буквой начинается заключительное подслово . Путь преодоления возникающей неоднозначности указан далее, в п.3.

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

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

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

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

В отличие от недетерминированных автоматов, конечные автоматы, введенные в предыдущем пункте, именуем детерминированными. Детерминированный конечный автомат является частным случаем недетерминированного, он получается из последнего в предположении, что все множества g*(q_i,а_j) являются одноэлементными.

Будучи запущен в работу над произвольным словом  из своего начального состояния, недетерминированный конечный автомат может функционировать по-разному. Язык L(К*), распознаваемый недетерминированным конечным автоматом К*, определяем следующим образом: слово принадлежит языку L(К*) тогда и только тогда, когда имеется последовательность состояний автомата

т

акая, что

.
. .

Иными словами, слово  принадлежит языку L(К*) тогда и только тогда, когда существует способ работы данного автомата над данным словом такой, что после завершения обработки  автомат оказывается в состоянии, принадлежащем множеству F.

На рис. 3.1 дан пример недетерминированного конечного автомата К₁* (причина недетерминированности заключается в том, что под воздействием буквы а автомат из состояния q₀ может либо перейти в состояние q₁, либо остаться в состоянии q₀). Легко видеть, что язык L(К₁*) совпадает с ранее введенным регулярным языком L₄.




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

По произвольному недетерминированному конечному автомату К*={Q, A, q₀, g*, F}, распознающему язык L(К*), детерминированный автомат К={Q, A, q₀, g, F} такой, что L(К)=L(К*), строим следующим образом. Полагаем Q=2^Q\, т.е. состояниями автомата К считаем непустые подмножества состояний автомата К*, при этом определяем q₀={q₀}. Функцию переходов автомата К строим таким образом, чтобы, обработав из q₀ произвольное слово , этот автомат приходил в состояние, представляющее собой подмножество состояний исходного автомата К*, в каждое из которых К* может перейти из своего начального состояния в результате обработки некоторым способом данного слова . Достижение указанной цели обеспечивается следующим определением функции g:

Так как слово  принадлежит L(К*) тогда и только тогда, когда существует способ работы автомата К* над данным словом такой, что после завершения обработки  автомат оказывается в одном из состояний множества F, совокупность F определяем следующим образом: произвольное состояние q_iF тогда и только тогда, когда q_iF.

Построенный изложенным способом детерминированный конечный автомат распознает тот же язык, что и исходный автомат К*. Теорема доказана.

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

Два автомата называем эквивалентными, если они распознают один и тот же язык. Согласно изложенному в доказательстве теоремы 3.1 алгоритму, для недетерминированного конечного автомата с N состояниями всегда можно построить эквивалентный ему детерминированный конечный автомат, имеющий 2^N–1 состояние. В действительности число требуемых состояний может оказаться меньшим. На рис. 3.2 представлен недетерминированный автомат К*, имеющий 3 состояния. Диаграмму переходов эквивалентного ему детерминированный конечного автомата К (см. рис. 3.3) строим следующим образом. Вводим вершину - состояние {q₀}. Из своего начального состояния q₀ автомат К^* по букве а либо переходит в q₁, либо остается в q₀; по букве b автомат переходит в q₂. Поэтому автомат К по букве а из {q₀} переходит в состояние {q₀,q₁}, а по букве b переходит в состояние {q₂}. Из состояний совокупности {q₀,q₁} по букве а автомат К* переходит в состояния той же совокупности, а по букве b как из состояния q₀, так и из состояния q₁ реализуется переход в q₂. Поэтому автомат К по букве а из {q₀,q₁} переходит в то же состояние {q₀,q₁}, а по букве b переходит в состояние {q₂}. Из состояния q₂ автомат К* по букве а переходит в q₀, а по букве b – остается в q₂. Поэтому автомат К по букве а из {q₂} переходит в {q₀}, а по букве b – остается в {q₂}. Построение автомата К закончено. Другие мыслимые состояния-подмножества оказываются излишними, они недостижимы; начав работу из своего начального состояния, автомат может оказываться только в трех введенных состояниях (включая начальное).

Концепция недетерминированного конечного автомата легко применяется для построения автомата, распознающего объединение двух регулярных языков. Пусть L₁ и L₂ – регулярные языки, распознаваемые конечными автоматами К¹={Q¹, A, q¹₀, g¹, F¹} и К²={Q², A, q²₀, g², F²} соответственно. Пусть D₁ и D₂ – диаграммы переходов, определяющие эти конечные автоматы. Для построения диаграммы переходов D автомата, распознающего объединение языков L₁ и L₂, объединяем эти диаграммы следующим образом. Вводим новую вершину - состояние q₀. По каждой букве х входного алфавита А из q₀ проводим две дуги с надписанной буквой х; верхняя дуга имеет своим концом вершину g¹(q¹₀,х), т.е. состояние, в которое переходит из своего начального состояния под воздействием буквы х первый автомат, а нижняя – вершину g²(q²₀,х), т.е. состояние, в которое переходит из своего начального состояния под воздействием буквы х второй автомат. Начальным состоянием построенного автомата считаем q₀; множество F его «хороших» состояний определяем как объединение множеств F¹ и F². Специально отметим, что в случае, когда хотя бы в одном из автоматов К¹, К² начальное состояние является «хорошим», в F следует включить состояние q₀. На первом такте обработки любого непустого входного слова =х автомат имеет возможность перехода из q₀ либо по верхней, либо по нижней дуге с надписанной буквой х. Если реализован переход по верхней дуге, то далее фактически работает автомат К¹ и проверяется принадлежность слова  языку L₁; если реализован переход по нижней дуге, далее работает автомат К² и проверяется принадлежность слова  языку L₂; построенный автомат в результате обработки произвольного входного слова  может оказаться в состоянии, принадлежащем подмножеству F, тогда и только тогда, когда  принадлежит объединению языков L₁ и L₂. На рис. 3.4 представлена диаграмма переходов построенного по изложенной схеме недетерминированного конечного автомата, распознающего множество чисел, каждое из которых кратно 2 или 5.

В заключение отметим, что для любых слов ,  и  в произвольном алфавите А определяемый ими язык L^_, (см. п.2) является регулярным. Диаграмма (вообще говоря, недетерминированного) конечного автомата, определяющего этот язык, строится аналогично представленной на рис. 2.13 диаграмме автомата, определяющего язык L^abc_bca,cab.