Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 11

Пусть A = (К, ∑, δ, p0, F) - произвольный конечный автомат. Построимавтомат:A1 = (K ∪ {q0}, Σ, δ ∪ {q0a → pi | p0a → pi ∈ δ}, q0, F ∪ {q0 | p0 ∈ F}).Любая цепочка x = a1 a2 ... ak принадлежит языку L(A) тогда и только тогда, когдасуществует следующая последовательность команд автомата А:p0a1 → p1; p1a2 → p2; . . . ; ph-1ah → ph, ph ∈ Fи соответствующая ей последовательность команд автомата А1:pk-1ak → ph.q0a1 → p1; p1a2 → p2; . . . ;Таким образом, имеем: A = A1.Теорема. Для произвольного конечного автомата существует эквивалентный автомат безциклов в заключительном состоянии.Доказательство. Будем считать, что автомат не имеет циклов в начальном состоянии.Сопоставим заданному произвольному конечному автомату A = (К, ∑, δ, p0, F) новыйавтомат A1:A1 = (K∪{f}, Σ, δ∪{qja → f | pja → pi∈δ & pi∈F}, p0, {f}∪{p0 | p0 ∈ F}).В результате имеем: A = A1.Теорема.

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

Операция итерации реализуется удалением циклов из начальных и заключительныхсостояний и объединения полученных состояний. Объединение начального изаключительного состояний означает, что построенный автомат допускает пустую цепочку.Однократный переход из начального в заключительное состояние исходного автоматасоответствует допуску цепочек языка L. Поскольку эти состояния объединены, автоматдопускает цепочки языков LL, LLL и т.д., т.е.

он распознает язык {ε}∪L∪L2∪ . . . =L*.2. Операция произведения над L(A1) и L(A2) выполняется с помощью двухпреобразований: а) удаляются циклы из начального состояния A2 и заключительногосостояния A1; б) каждому заключительному состоянию A1ставим в соответствие свойэкземпляр A2 и объединяем заключительные состояния A1 с начальным состояниемсоответствующего экземпляра A2.3. Объединение L(A1) и L(A2) строится с помощью удаления циклов в начальныхсостояниях A1 и A2 и объединения полученных начальных состояний.4. Усеченная итерация может быть построена двумя способами:а) L(A1)+ = L(A1)* L(A1),б) L(A1)+ = L(A1) L(A1)*.5.

Рассмотрим дополнение L(A1) до Σ*. Пусть автомат A1 детерминированный, тогдалюбая цепочка x=a1a2 . . an распознается по единственному маршруту:p0a1 → p1p1a2 → p2. . .pn-1an → pn, pn∈ F.Автомат не распознает только те цепочки, которые:1) либо представляют собой начальную часть цепочки a1a2 . . aj, при чтении которойавтомат переходит в состояние, не являющееся заключительным;2) либо имеют вид y = a1a2 . . akbc1c2 .

. cm (k < n), где начало цепочки a1a2 . . ak совпадает сначалом цепочки x∈L(A1), но за символом ak стоит такой символ b, что автомат A1 егопрочитать не может.Поэтому для того чтобы построить автомат, распознающий дополнение языка,необходимо:а) все заключительные состояния сделать незаключительными, а незаключительныесостояния - заключительными;б) ввести дополнительное состояние, сделать его заключительным и из каждогосостояния провести в это состояние такие дуги, каждая из которых соответствует символамалфавита, не читаемым в этом состоянии;в) в построенном дополнительном состоянии построить петли для всех символовалфавита, чтобы обеспечить чтение произвольного окончания цепочки c1c2 . .

cm.6. Разность L(A1) и L(A2) строится в соответствии со следующим преобразованием:L(A1) \ L(A2) = L(A1) ∩ L(A2) .7. Операция пересечения строится в соответствии со следующим преобразованием:L(A1) ∩ L(A2) = L(A1) ∪ L(A2) .На основании этой теоремы можно строить конечные автоматы, последовательносинтезируя их на основе уже построенных автоматов.5.3.4. Автоматные грамматикиЛинейные грамматики (праворекурсивные и леворекурсивные) называются автоматнымиграмматиками, так как языки, порождаемые ими, совпадают с языками, распознаваемымиконечными автоматами.Рассмотрим ряд теорем.Теорема. Для каждой праволинейной грамматики существует эквивалентный конечныйавтомат.Доказательство. Каждому нетерминалу произвольной праволинейной грамматики Gпоставим в соответствие одно состояние конечного автомата A.

Добавим еще одно состояние- единственное конечное состояние. Состояние, соответствующее аксиоме, назовемначальным состоянием.Каждому правилу A→aB поставим в соответствие команду Aa → B, а каждомутерминальному правилу A → a поставим в соответствие команду Aa → F.Таким образом, выводу цепочки в грамматикеS ⇒ a1A1 ⇒ a1a2A2 ⇒ ... ⇒ a1a2...ak-1Ak-1⇒ a1a2...ak взаимно однозначно соответствуетпоследовательность команд построенного автомата A:Aa1 → A1; A1a2 → A2; . .

. ; Ak-1ak → F. Таким образом, язык L(G) = L(A).Пример. Пусть для заданной грамматики G требуется построить конечный автомат.S → aS | bB;A → aA | bS;B → bB | с | cA.Решение. Граф автомата будет иметь четыре вершины, три из них помеченынетерминальными символами грамматики S, A, B, четвертая вершина, помеченная символомF, является единственным заключительным состоянием. Начальным состоянием являетсявершина, соответствующая аксиоме S.abSbBbcAcFaКаждому правилу грамматики поставим в соответствие команду конечного автомата:Sa → S - в начальном состоянии при поступлении на вход терминального символа аавтомат остается в том же состоянии S;Sb → B - из начального состояния при поступлении на вход терминала b автоматпереходит в состояние B;Bb → B - в состоянии В при поступлении на вход терминала b автомат остается в том жесостоянии B;Bc → F - из состояния В при поступлении на вход терминала c автомат переходит взаключительное состояние F;Bc → A - из состояния В при поступлении на вход терминала c автомат переходит всостояние А;Aa → A - в состоянии А при поступлении на вход терминала а автомат остается в этомже состоянии А;Ab → S - из состояния A при поступлении на вход терминала b автомат переходит всостояние S.Полученный недетерминированный конечный автомат распознает цепочки языка,порождаемые праворекурсивной грамматикой G.Теорема.

Для произвольного конечного автомата существует эквивалентнаяправолинейная грамматика.Доказательство. Каждому состоянию произвольного автомата поставлен в соответствиенетерминал грамматики, причем начальному состоянию будет соответствовать аксиома.Тогда для каждой команды Ac → B в множество правил грамматики включим правило A→ cB, причем в случае, если B - заключительное состояние, добавим правило A → c.Эквивалентность исходного конечного автомата и построенной грамматики очевидна.Теорема.

Для каждой леворекурсивной грамматики существует эквивалентныйконечный автомат.Доказательство. Каждому нетерминальному символу произвольной леворекурсивнойграмматики поставим в соответствие состояние конечного автомата, причем состояние,соответствующее аксиоме S, сделаем заключительным. Добавим еще одно состояние N исделаем его начальным состоянием.Каждому правилу грамматики A → Ba поставим в соответствие команду автомата Вa →A. Тогда каждому выводу в грамматике:S⇒A1ak⇒A2ak-1ak⇒ ...

⇒Ak-1a2a3...ak ⇒ a1a2 . . . ak однозначно соответствуетследующая последовательность команд построенного автомата A:Na1 → Ak-1; . . .; A2ak-1 → A1; A1ak → S.Таким образом, язык L(G) = L(A).Теорема. Для произвольного конечного автомата существует эквивалентнаялеворекурсивная грамматика.Доказательство. Каждому состоянию произвольного автомата поставим в соответствиенетерминальный символ грамматики, добавим нетерминал S и сделаем его аксиомой.Каждой команде Aa → B в множество правил включим соответствующее правило B →Aa, причем в том случае, если B - заключительное состояние, дополнительно введем правилоS → Aa, а если A - начальное состояние, то дополнительно введем правило B → a.Тогда последовательности команд:A0a1 → A1; A1a2 → A2; . .

. ; Ak-1ak → Fсоответствует следующий вывод:S ⇒ Ak-1ak ⇒ ... ⇒ A1a2a3...ak ⇒ a1a2a3...ak.Важной особенностью автоматных грамматик является возможность представления их спомощью конечных графов. По графу грамматики легко отыскивается вывод нужнойцепочки.Любой вывод цепочки в автоматной грамматике соответствует пути в графе этойграмматики, который начинается из вершины S (вершины, помеченной аксиомой) изаканчивается в конечной вершине.Пример. Построить конечный автомат, распознающий язык L(A) = {(ab)*}.Сначала построим некоторую грамматику G, которая бы порождала язык L(A):S → aA;A → bS | b.Проверим, действительно ли эта грамматика порождает язык L(A).