А.А. Вылиток - О регулярных языках (1115013)
Текст из файла
А. А. ВылитокО регулярных языкахРегулярные языки играют важную роль в математических теориях и вприложениях. К наиболее известным формализмам, описывающим регулярные языки,относятся: регулярные выражения, конечные автоматы, регулярные грамматики.Определение. Пусть Σ — алфавит, не содержащий символов *, +, ε, ∅, (, ).Определим рекурсивно регулярное выражение γ над алфавитом Σ и регулярный языкL(γ), задаваемый этим выражением:1) a ∈ Σ ∪ {ε, ∅} есть регулярное выражение; L(a) = {a} для a ∈ Σ ∪ {ε};L(∅) = ∅;2) если α и β — регулярные выражения, тоа) (α) + (β) — регулярное выражение;L((α) + (β)) = L(α) ∪ L(β);б) (α)(β) — регулярное выражение;L((α)(β)) = L(α)L(β);*в) (β) — регулярное выражение;L((β)*) = (L(β))*;3) все регулярные выражения конструируются только с помощью пунктов 1 и 2.Если считать, что операция «+» имеет самый низкий приоритет, а операция«*» — наивысший, то в регулярных выражениях можно опускать лишние скобки.Примеры регулярных выражений над алфавитом {a, b}: a + b, (a + b)*, ((a)*b)*.Соответствующиеязыки:L(a + b) = {a} ∪ {b} = {a, b},L((a + b)*) = {a,b}*,L(((a)*b)*) = { x1bx2b...xkb | k ≥ 1, xi ∈ {a}* для i = 1, ..., k} ∪ {ε}.Определение.
Недетерминированный конечный автомат (НКА) — это пятеркаA = (K, Σ, δ, I, F), где:К — конечное множество состояний, или вершин;Σ — входной алфавит (также конечный);δ ⊆ K × Σ × K — множество команд, или дуг;I ⊆ K — множество начальных состояний;F ⊆ K — множество заключительных состояний.Множество δ можно также интерпретировать как отображение K × Σ вмножество подмножеств K.Существуют алгоритмы, позволяющие по регулярному выражению построитьэквивалентный (т. е.
определяющий тот же язык) конечный автомат, и наоборот, поавтомату построить эквивалентное ему выражение.Пример 1. A1 = ({A, B, C, D, E}, {a, b}, δ, {A, D}, {C, E}), где δ = {(A, a, B), (D, a,E), (B, b, C), (E, b, C), (C, b, C)}.Автомат удобно представлять в виде ориентированного размеченного графа:AabBCbbDaEВходящими непомеченными стрелками отмечены начальные вершины A и D,исходящими — заключительные вершины E и C.Каждая дуга НКА A имеет пометку из Σ.
Путь в ориентированном графе можетбыть представлен последовательностью дуг. Пустой путь можно представить однойвершиной, которая считается одновременно началом и концом пути. Пометка пути —это сцепление (конкатенация) пометок его дуг. Пустой путь имеет пустую пометку.Путь из начальной вершины в заключительную называется успешным. Язык,допускаемый автоматом A (обозначается L(A)), — это множество пометок всехуспешных путей автомата.Приведем примеры путей автомата A 1 (см. пример 1):bbb(а) путь E ⎯⎯→C⎯⎯→C⎯⎯→C имеет пометку bbb;(б) пустой путь А имеет пометку ε;a(в) путь D ⎯⎯→ E является успешным и имеет пометку a;abbb(г) путь A ⎯⎯→ B ⎯⎯→ C ⎯⎯→ C ⎯⎯→ C является успешным и имеет пометкуabbb.Язык, допускаемый автоматом A 1: L(A 1) = {abn | n ≥ 0} = L(ab*)Заметим, что ε ∈ L(A) если и только если A имеет вершину, являющуюсяодновременно начальной и заключительной.Еще один способ задать регулярный язык — описать его с помощью регулярнойграмматики (грамматики типа 3 по классификации Хомского). Грамматика называетсярегулярной, если она либо праволинейна, либо леволинейна.Грамматика праволинейна, если каждое ее правило относится к одному из трехвидов правил: A → aB, A → a, A → ε, где A, B — означают нетерминалы, а означаеттерминальный символ, ε — пустая цепочка.
Грамматика леволинейна, если ее правилаимеют вид: A → Ba, A → a, A → ε.Заметим, что иногда в литературе, описывающей практическое применениерегулярных грамматик, в этих грамматиках не допускаются правила вида A → ε. Этоограничение вполне оправдано. Например, синтаксис лексем языка программированиявсегда можно описать грамматикой без ε-правил, так как не существует пустых лексем.Существуют способы преобразования регулярной грамматики в эквивалентныйконечный автомат и наоборот — конечного автомата в регулярную грамматику.Алгоритм построения НКА по праволинейной грамматике1.
Множество вершин НКА состоит из нетерминалов грамматики и еще одной новойвершины F, которая объявляется заключительной.2. Каждому правилу вида А → аВ в автомате соответствует дуга из вершины А вa⎯→ B . Каждому правилу вида A → aвершину В, помеченная символом а: A ⎯aсоответствует дуга A ⎯⎯→F . Других дуг в автомате нет.3. Начальной вершиной автомата является вершина, соответствующая начальномусимволу грамматики.
Вершина В является заключительной, если в грамматике естьправило В → ε. Кроме того, заключительной является F, построенная на шаге 1.abПример 2. G2: S → aS | aA | εA(G2): SaAA → b | bAn mL(G)={a b | n ≥ 1, m ≥ 1} ∪ {ak | k ≥ 0} = L(a*(ε + ab*b))b FАлгоритм построения НКА по леволинейной грамматике1.
Множество вершин НКА состоит из нетерминалов грамматики и еще одной новойвершины Н, которая объявляется начальной.2. Каждому правилу вида А → Ва в автомате соответствует дуга из вершины В вa⎯→ A . Каждому правилу вида А → авершину А, помеченная символом а: B ⎯aсоответствует дуга H ⎯⎯→A . Других дуг нет.3. Заключительной вершиной автомата является вершина, соответствующаяначальному символу грамматики. Вершина B является начальной, если в грамматикеесть правило B → ε.
Кроме того, начальной является вершина H, построенная нашаге 1.A(G3):bПример 3. G3: S → Ab | εA → Aa | BbbH aBB → Bb | aL(G3) = {abnamb | n ≥ 1, m ≥ 0} ∪ {ε} = L(ab*ba*b + ε)aAbSДля любого НКА, имеющего несколько начальных вершин, можно построитьэквивалентный ему НКА с единственной начальной вершиной. По такому автоматулегко построить эквивалентную праволинейную грамматику.Алгоритм построения праволинейной грамматикипо НКА с единственной начальной вершиной1. Нетерминалами грамматики будут вершины автомата, терминалами — пометки дуг.a2. Для каждой дуги вида A ⎯⎯→ B в грамматику добавляется правило А → аВ. Длякаждой заключительной вершины B в грамматику добавляется правило В → ε.3.
Начальным символом является нетерминал, соответствующий начальной вершине.4. К построенной по пунктам 1—3 грамматике применить алгоритм устранения εправил, затем — алгоритм удаления бесполезных символов (приведенияграмматики).Пример 4.A4:aSabBFbПосле шага 3: S → aS | aB G(A4): S → aS | aBB → bB | aFB → bB | aF→εДля построения леволинейной грамматики по НКА, НКА следует сначалапреобразовать в эквивалентный автомат с единственной заключительной вершиной(такое преобразование всегда возможно).Алгоритм построения леволинейной грамматикипо НКА с единственным заключительным состоянием1.
Нетерминалами грамматики будут вершины автомата, терминалами — пометки дуг.a⎯→ B в грамматику добавляется правило В → Аа. Для каждой2. Для каждой дуги A ⎯начальной вершины В в грамматику добавляется правило В → ε.3. Начальным символом будет нетерминал, соответствующий заключительнойвершине.4. К построенной по пунктам 1—3 грамматике применить алгоритм устранения εправил, затем — алгоритм приведения грамматики.Пример 5.A 5:BaaCПосле шага 3: A → Ca | AbC → Cb | BaB→εAbbG(A5):A → Ca | AbC → Cb | aОпределение. Конечный автомат называется детерминированным конечнымавтоматом (ДКА), если он имеет единственное начальное состояние, и любые две дуги,исходящие из одной и той же вершины имеют различные пометки.Все автоматы в примерах 1—4 не являются детерминированными.Для каждого НКА можно построить эквивалентный ему детерминированныйконечный автомат.Алгоритм построения ДКА по НКАВход: A′ = (K′, Σ, δ′, I, F) — НКА.Выход: A = (K, Σ, δ, InitState, FinalStates) — ДКА.Метод: Вершинами (состояниями) автомата A будут подмножества множестваК′ автомата A′.
CurState и NewState — вспомогательные переменные для хранениятаких подмножеств. Сам алгоритм запишем в паскалеподобном стиле. Фигурныескобки означают конструкторы множеств.begin InitState := {s | s ∈ I}; K := {InitState}; δ := ∅;while (в К есть нерассмотренный элемент)beginCurState := нерассмотренный элемент из К;for (каждого а ∈ Σ)begina⎯→ q ) ∈ δ, p ∈ CurState};NewState := {q | ( p ⎯K := K ∪ {NewState};aδ := δ ∪ {(CurState ⎯⎯→ NewState)};endend;FinalStates := {P ∈ K | существует q ∈ P: q ∈ F }end.abaПример 6.A6′:a,b12b3bПроцесс построения удобно изобразить в виде таблицы, начав с состояния {1, 2}символсостояниеab{1, 2}{2, 3}{1, 2, 3}{2, 3}{2, 3}{2, 3}{1, 2, 3}{1, 2, 3}{1, 2, 3}Обозначим состояние {1, 2} через A, {2, 3} — B, {1, 2, 3} — C.С учетом переобозначений построим по таблице ДКА A 6 :AabbbCBaL(A6)={a, b}+aМожно заметить, что язык L = {a, b}+, допускаемый автоматом A6, допускаетсятакже ДКА A6′′, имеющим только два состояния.A6′′:1a,b2a,bСуществует алгоритм, позволяющий по любому ДКА построить эквивалентныйДКА с минимальным числом состояний.Работу детерминированного конечного автомата можно промоделировать спомощью компьютерной программы.
К такого рода программам относятся, например,лексические анализаторы. В основе анализатора лежит автомат, задающий синтаксислексем некоторого языка. Заметим, что в детерминированном автомате A = (K, Σ, δ, I,F) δ можно интерпретировать как частичную функцию из K × Σ в K. Доопределим δ навсем множестве K × Σ. Для этого добавим в K ещё одно состояние ERR (переходавтомата в это состояние будет означать, что входная цепочка не допускается (т.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
