Мастихина А.А. Формальные языки и автоматы, для РК-6, страница 3

Также онпорождает тот же язык, что и И, так как любому слову, приписанномупути в И из некоторой начальной вершины в некоторую заключительную, соответствует путь в Д и наоборот.Пример.Слева — источник И , справа — процесс его детерминизации.b?10aa - 40 a, b20a -·{1, 2}∅{3}∗Hb1 a 3 HHHj y5bb*0b??a- 40- 4b - 003 {4, 5} a ∅5 {3, 5}∅∗·42bb?a- 40?006 {5}∅5 {3, 5}b?40∅Детерминированный источник выглядит так:b?ay5b @ a ?a @b∗ a -`@` ?R@124 6a@ba b@R@b- y 6y3612Детерминированный источник без выделенных заключительных вершин и такой, что каждому ребру сопоставлена еще и буква некоторого"выходного" алфавита, задает по определению инициальный автомат.6Автоматы.Определение и способы задания.Рассмотрим алфавит A — входной алфавит, его элементы — входныебуквы, алфавит V — выходной алфавит, его элементы — выходные буквы. Составленные из этих букв слова называются соответственно входными и выходными.

Также вводится Q — множество (алфавит) состояний. В дальнейшем буквы из A, V, Q будем обозначать, соответственно,через a, b, ...; x, y, .. и q0 , q1 , q2 ....Чтобы определить автомат, нужно задать, в каких состояниях автомат будет находиться в зависимости от поступившей последовательностивходных букв, и какие выходные буквы будет выдавать.Конечным неинициальным автоматом называется пятеркаA = (A, Q, V, ϕ, f ) ,где Q×A → Q — функция переходов, f : Q×A → V — функция выходов.Если выделено начальное состояние q0 , автомат (A, Q, V, ϕ, f, q0 ) называется инициальным.Если в момент времени t на вход автомату A поступает буква x(t),на выходе получается некоторая буква y(t), и qt означает состояние автомата в момент времени t, то функционирование автомата может бытьзадано следующей системой уравнений:y(t) = f (qt−1 , x(t)),qt = ϕ(qt−1 , x(t)).Также распространены способы задания в виде диаграммы Мура илитаблицы.Диаграмма Мура изображается как ориентированный псевдограф,где вершины — состояния, из каждого состояния выходят ровно |A| ребер, и на каждом из них написана одна из входных букв (разным ребрам— разные буквы).

Через запятую пишется выходная буква (выход приданных входной букве и состоянии, из которого выходит ребро). То естьдиаграмма Мура выглядит как детерминированный источник без заключительных вершин, но с выходными значениями.Начальное состояние (для инициального автомата) обозначается звездой.13b, ya, xa, yq1 - - q2?a, yq0 b, x b, y∗ IВ таблице отображаются новое состояние и выходная буква при заданных входной букве и текущем состоянии.qQx Q q1Qqjqsa1aiϕ(qj , ai ), f (qj , ai )anПример различных представлений автомата.Рассмотрим автомат A, для которого все три алфавита A, V, Q совпадают с {0, 1}.

Таким образом,A = ({0, 1}, {0, 1}, {0, 1}, ϕ, f ) .Функции f, ϕ зададим формулами f (q, a) = q, ϕ(q, a) = q ⊕ a, где ⊕есть сложение по модулю 2.Система уравнений для данного автомата такова:y(t) = f (qt−1 , x(t)) = qt−1 ,qt = ϕ(qt−1 , x(t)) = qt−1 ⊕ x(t).Изобразим тот же автомат в виде диаграммы и в виде таблицы.140, 0Q qQ0xQ0, 11, 1- 101, 0100, 01, 111, 00, 1Этот автомат осуществляет задержку входной буквы на один такт.Отображение языков, задаваемое автоматом.Пусть дан инициальный автомат.

Возьмем произвольное слово α из∗A , α = a(1)a(2)...a(r). Рассмотрим в диаграмме Мура путь, начинающийся в начальной вершине q0 , дальше ведущий по ребру a(1), потомпо a(2) и так далее до a(r). Выпишем последовательно буквы выходногоалфавита, написанные на этих ребрах: v(1)...v(r) ∈ V ∗ .Получится отображение Φ : A∗ → V ∗ , Φ(a(1)...a(r)) = v(1)...v(r), вчастности, Φ(Λ) = Λ.Пример.-a, 1b, 0 ? ∗q0 a, 0q1b, 1?Φ(a3 b2 ) = 10111Φ(an ) = |1010...{z }nДва автомата с одними и теми же входными и выходными алфавитами называются эквивалентными, если задаваемые ими отображениясовпадают.Автомат Мура.Для распознавания языков удобно использовать автомат следующего вида: для каждого состояния qi ∈ Q на всех ребрах, входящих в qi ,написана одна и та же буква выходного алфавита V (V -метка).Диаграмму в этом случае можно изображать проще: состояния изображаются в виде круга, внуть которого вписана V -метка.

На ребрах выходные метки не отображаются.Например, для автомата из предыдущего примера муровский автомат выглядит так:15b?-a∗ 0a1b?Теорема.Для любого автомата можно построить эквивалентный ему муровский автомат.Доказательство.Рассмотрим состояние qi и ребра, в него входящие. Возможны дваслучая:1) На всех входящих ребрах V -метки одинаковые. Назовем такое состояние простым.

Тогда стираем метки на ребрах и пишем это выходноезначение в состоянии. Таким образом, простому состоянию обычного автомата соответствует одно состояние муровского автомата.2) V -метки разные. Назовем такое состояние сложным. Пусть число различных V -меток, написанных на ребрах, входящих в вершину qi ,равно k. Тогда в муровском автомате состоянию qi будет соответствоватьровно k состояний. В каждом из k состояний своя V -метка, и в него ведутребра, входившие в qi в исходном автомате с этой V -меткой. qi стираем,а ребра, выходившие из него, выводим из каждой новой вершины.Так преобразуется каждое сложное состояние qi :a, xq1x QsQb, y q2 HQHa a,3x QQ 2jHq3 -b H y -b, y Q q...-a, x qi -a, x q 1a,y @*@q2 R b, y@@q 2q3 b, yq1q1...-a...В частности, если в сложном состоянии есть петля, расщепление происходит так:b, yq1 -a, y qi -b, y q 1q1xa6a6 b, ya, xy 3q -b1Процедура проделывается для каждого состояния. В итоге получается муровский автомат, эквивалентный данному.Язык, создаваемый муровским автоматом.Рассмотрим инициальный автомат с выходным алфавитом B = {0, 1}и произвольным входным алфавитом A.

Построим для него детерминированный источник, взяв тот же ориентированный псевдограф. Состоя16ния муровского автомата, в которых написано 1, назовем заключительными вершинами. Начальная вершина — q0 (начальное состояние автомата). Этот источник порождает некоторый язык L.Итак, любой автомат с выходным алфавитом {0, 1} задает детерминированный источник, и ясно, что это соответствие взаимно-однозначно.Таким образом, указанный автомат задает язык L ⊆ A∗ .

(Говорят также, что автомат распознает или допускает язык.) Язык, для которогосуществует распознающий его автомат, называется автоматным.Таким образом, автомат распознвет язык L с помощью выделенного символа выходного алфавита: слова из L он преобразует в выходныеслова, которые заканчиваются на 1, а слова не из L — в слова, заканчивающиеся на 0.Язык, распознаваемый рассмотренным выше муровским автоматом— все слова, в которое a входит нечетное число раз.Переформулируем теоремы Клини следующим образом.Теорема Клини (для автоматов)1) Любой регулярный язык является автоматным.2) Любой автоматный язык является регулярным.Таким образом, совпадают следующие классы языков:1) регулярные,2) автоматные,3) задаваемые грамматикой.Причем в каждом случае представление языка не единственно.

Нодля конечных автоматов существует алгоритм, находящий оптимальныйпо числу состояний автомат. Этот алгоритм будет описан в следующемразделе.7Минимизация автоматов.Так как существуют различные автоматы, задающие одинаковые отображения Φ, возникает вопрос, как построить автомат, эквивалентныйданному, но с меньшим числом состояний. Процесс минимизации позволяет получить автомат с наименьшим числом состояний.Состояния qi и qj некоторого автомата называются эквивалентными,если инициальные автоматы с начальными состояниями qi и qj эквивалентны.Разобьем множество состояний автомата Q на классы эквивалентности (эквивалентные состояния находятся в одном классе, состояния из17разных классов неэквивалентны).

Каждый класс объявляется состоянием нового автомата qe1 , qe2 , ..., qes . От состояния qei к состоянию qej проводится ребро с буквами a, v, если такие ребра были между состояниямиисходного автомата из соответствующих классов.qe — начальная вершина, если в соответствующем классе содержитсяначальная вершина.Полученный автомат называется минимальным или приведенным.Разбиение на классы происходит следующим образом.Алгоритм минимизации.1) qi , qj отнесем к одному классу, если f (qi , a) = f (qj , a) для каждой буквы входного алфавита. Полученный класс назовем классом 1эквивалентности.2) Каждый полученный класс разобьем следующим образом:qs , qt из класса 1-эквивалентности находятся в одном классе 2эквивалентности, если для каждой буквы входного алфавита a состояния ϕ(qs , a) и ϕ(qt , a) находятся в одном классе 1-эквивалентности длякаждого a.i) qs , qt из одного класса (i − 1)-эквивалентности находятся в одномклассе i-эквивалентности, если для каждого a состояния ϕ(qs , a) и ϕ(qt , a)находятся в одном классе (i − 1)-эквивалентности.Когда этот процесс остановится (классы прекращают делиться), получится требуемое разбиение.

Легко видеть, что максимальное число шагов данного алгоритма на единицу меньше числа состояний исходногоавтомата.Пример.a, x∗ - q1b, y q0q0?? a, xI b,xa, y b, xq1q2aq2 , y q 0 , x q 0 , xbq1 , y q 2 , x q 1 , xq2На первом шаге алгоритма (проверка совпадения выходных символов) выделяются два класса: I = {q0 }, II = {q1 , q2 }. Рассмотрим ϕ(qi , aj )для второго класса.18q1q2aIIbIIIIФункции переходов переводят состояния в одинаковые классы, дальше разбиения не происходит.

Значит, состояния q1 и q2 эквивалентны.Минимальный автомат имеет вид:-b, y∗a, y - b, x?q0q1,2 a, xПример.Задание: по грамматике построить источник, детерминировать его,получить автомат, распознающий тот же язык, минимизировать полученный автомат и записать грамматику для минимального автомата.I → aI|bI|bA,A → aB|bC,B → aB|bI|aI,C → bC|a|b.Источник, порождающий тот же язык, что и грамматика.b-4b @@aa 1@RR R@ 5∗ b -2tb6@aa@Ib@IbaR3@6Детерминируем этот источник.191=I2=A3=B4=C10∗{1}0b40{1, 2, 4}b-2- {1,2}bb - 6060{1, 2, 4, 5}{1, 2, 4, 5}aaaa??30{1, 3}?50{1, 3, 5}?bb10{1}a{1, 3} ?30 20{1, 2}50{1, 3, 5}@a0@@R 3{1, 3}?20{1, 2}Детерминированный источникимеет видaa3w5 66a 1∗6a baab - w- ?b2b4b66bТакому источнику можно поставить в соответствие муровский автомат, допускающий тот же язык с помощью выходного символа 1.123456a 1,0 3,0 3,0 5,1 3,0 5,1b 2,0 4,0 2,0 6,1 2,0 6,1На первом шаге выделяютя классы 1-эквивалентности:I = {1, 2, 3, 5}, II = {4, 6}1a Ib I2III3II4III5II6IIIКлассы 2-эквивалентности:I = {1, 3, 5}, II = {2}, III = {4, 6}201a Ib II23IIIII II45IIIII II6IIIIМинимизация закончена.