Недетерминированные конечные автоматы

Формальные языки

Определение 1.1.1. Будем называть натуральными числами неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2,...} обозначается N.

Определение 1.1.2. Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами).

Определение 1.1.3. Словом (цепочкой, строкой, string) в алфавите называется конечная последовательность элементов .

Пример 1.1.4. Рассмотрим алфавит = {a, b, c}. Тогда baaa является словом в алфавите .

Определение 1.1.5. Слово, не содержащее ни одного символа (то есть последовательность длины 0), называется пустым словом и обозначается .

Определение 1.1.6. Множество всех слов в алфавите обозначается .

Замечание 1.1.7. Множество счетно. В самом деле, в алфавите множество всех слов данной длины конечно, следовательно, является объединением счетного числа конечных множеств.

Определение 1.1.8. Множество всех непустых слов в алфавите обозначается .

Пример 1.1.9. Если = {a}, то = {a,aa,aaa,aaaa,...}.

Определение 1.1.10. Если , то L называется языком (или формальным языком) над алфавитом .

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом (обозначения ).

Пример 1.1.11. Множество {a, abb} является языком над алфавитом {a, b}.

Определение 1.1.12. Пусть . Тогда язык называется дополнением языка L относительно алфавита . Когда из контекста ясно, о каком алфавите идет речь, говорят просто, что язык является дополнением языка L.

Определение 1.1.13. Если x и y - слова в алфавите , то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией,(катенацией, сцеплением) слов x и y. Иногда конкатенацию слов x и y обозначают .

Определение 1.1.14. Если x - слово и , то через xⁿ обозначается слово . Положим (знак читается "равно по определению"). Всюду далее показатели над словами и символами, как правило, являются натуральными числами.

Пример 1.1.15. По принятым соглашениям ba³ = baaa и (ba)³ = bababa.

Пример 1.1.16. Множество является языком над алфавитом {a,b}. Этот язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.

Определение 1.1.17. Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.

Пример 1.1.18. Очевидно, что |baaa| = 4 и .

Определение 1.1.19. Через |w|_a обозначается количество вхождений символа a в слово w.

Пример 1.1.20. Если , то |baaa|_a = 3, |baaa|_b = 1 и |baaa|_c = 0.

Операции над языками

Определение 1.2.1. Пусть . Тогда

Язык называется конкатенацией языков L₁ и L₂.

Пример 1.2.2. Если L₁ = {a,abb} и L₂ = {bbc,c}, то .

Определение 1.2.4. Пусть . Тогда

Пример 1.2.5. Если L = {a^kba^l | 0 < k < l}, то L² = {a^kba^lba^m | 0 < k < l - 1, m > 1}.

Определение 1.2.7. Итерацией языка (Kleene closure) языка L (обозначение L^*) называется язык

Эта операция называется также звездочкой Клини (Kleene star, star operation).

Пример 1.2.8. Если и L = {aa,ab,ba,bb}, то

Определение 1.2.11. Обращением или зеркальным образом слова w (обозначается w^R) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.

Пример 1.2.12. Если w = baaca, то w^R = acaab.

Определение 1.2.13. Пусть . Тогда

Язык L^R называется обращением языка L.

Определение 1.2.15. Говорят, что слово x - префикс (начало) слова y (обозначение ), если y = xu для некоторого слова u.

Пример 1.2.16. Очевидно, что , , и .

Определение 1.2.17. Пусть . Тогда через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L:

Множество Pref(L) называется множеством префиксов языка L.

Определение 1.2.18 Говорят, что слово x - суффикс (конец) слова y (обозначение ), если y = ux для некоторого слова u.

Определение 1.2.19. Пусть . Тогда через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L:

Множество Suf(L) называется множеством суффиксов языка L.

Определение 1.2.20. Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v.

Определение 1.2.21. Пусть . Тогда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L. Множество Subw(L) называется множеством подслов языка L.

Определение 1.2.22. Слово a₁a₂...a_n (длины ) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u₀, u₁,..., u_n, что u₀a₁u₁a₂...a_nu_n = y.

Замечание 1.2.23. Все подслова слова y являются также подпоследовательностями слова y.

Определение 1.2.24. Пусть . Тогда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей языка L.

Пример 1.2.25. Рассмотрим язык L = { cba, c} над алфавитом {a, b, c}. Очевидно, что .

Определение 1.2.26. Функция называется биекцией (bijection), если каждый элемент множества Lявляется образом ровно одного элемента множества K (относительно функции f).

Определение 1.2.27. Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Гомоморфизмы

Определение 1.3.1. Пусть и - алфавиты. Если отображение удовлетворяет условию для всех слов и , то отображение h называется гомоморфизмом (морфизмом).

Замечание 1.3.2. Можно доказать, что если - гомоморфизм, то .

Замечание 1.3.3. Пусть и . Тогда отображение , заданное равенством , является гомоморфизмом.

Замечание 1.3.4. Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

Замечание 1.3.5. Если - гомоморфизм и , то через h(L) обозначается язык .

Пример 1.3.6. Пусть и гомоморфизм задан равенствами h(a) = abba и . Тогда

Определение 1.3.7. Если - гомоморфизм и , то через h^-1(L) обозначается язык .

Пример 1.3.8. Рассмотрим алфавит . Пусть гомоморфизм задан равенствами h(a) = ab и h(b) = abb. Тогда

Порождающие грамматики

Определение 1.4.1. Порождающей грамматикой (грамматикой типа 0, generative grammar, rewrite grammar) называется четверка , где N и - конечные алфавиты, , , P конечно и . Здесь - основной алфавит (терминальный алфавит), его элементы называются терминальными символами или терминалами (terminal), N - вспомогательный алфавит (нетерминальный алфавит), его элементы называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable), S - начальный символ (аксиома, start symbol). Пары называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде .

Пример 1.4.2. Пусть даны множества N = {S}, , . Тогда является порождающей грамматикой.

Замечание 1.4.3. Будем обозначать элементы множества строчными буквами из начала латинского алфавита, а элементы множества N - заглавными латинскими буквами. Обычно в примерах мы будем задавать грамматику в виде списка правил, подразумевая, что алфавит N составляют все заглавные буквы, встречающиеся в правилах, а алфавит - все строчные буквы, встречающиеся в правилах. При этом правила порождающей грамматики записывают в таком порядке, что левая часть первого правила есть начальный символ S.

Замечание 1.4.4. Для обозначения n правил с одинаковыми левыми частями часто используют сокращенную запись .

Определение 1.4.5. Пусть дана грамматика G. Пишем , если , и для некоторых слов в алфавите . Если , то говорят, что слово непосредственно выводимо из слова .

Замечание 1.4.6. Когда из контекста ясно, о какой грамматике идет речь, вместо можно писать просто .

Пример 1.4.7. Пусть

Тогда .

Определение 1.4.8. Если , где , то пишем и говорим, что слово выводимо из слова . Другими словами, бинарное отношение является рефлексивным, транзитивным замыканием бинарного отношения , определенного на множестве .

При этом последовательность слов называется выводом (derivation) слова из слова в грамматике G. Число n называется длиной (количеством шагов) этого вывода.

Замечание 1.4.9. В частности, для всякого слова имеет место (так как возможен вывод длины 0).

Пример 1.4.10. Пусть . Тогда . Длина этого вывода - 3.

Определение 1.4.11. Язык, порождаемый грамматикой G, - это множество . Будем также говорить, что грамматика G порождает (generates) язык L(G).

Замечание 1.4.12. Существенно, что в определение порождающей грамматики включены два алфавита - и N. Это позволило нам в определении 1.4.11 "отсеять" часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту .

Пример 1.4.13. Если , то .

Определение 1.4.14. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.4.15. Грамматика

и грамматика

эквивалентны.

Классы грамматик

Определение 1.5.1. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид , где , , , .

Пример 1.5.2. Грамматика

не является контекстной (последние три правила не имеют требуемого вида).

Определение 1.5.3. Контекстно-свободной грамматикой (бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид , где , .

Пример 1.5.4. Грамматика

является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Определение 1.5.5. Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид или , где , , , .

Грамматика

является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Определение 1.5.7. Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид или , где , , .

Пример 1.5.8. Грамматика

является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример 1.5.9. Грамматика

праволинейная. Она порождает язык .

Пример 1.5.10. Грамматика

праволинейная.

Пример 1.5.11. Грамматика

праволинейная. Обобщенный вариант языка, порождаемого этой грамматикой, используется в доказательстве разрешимости арифметики Пресбургера.

Определение 1.5.12. Правила вида называются - правилами или эпсилон-правилами.

Лемма 1.5.13. Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без -правил является контекстной грамматикой.

Определение 1.5.14. Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского (Chomsky hierarchy).

Определение 1.5.15. Язык называется языком типа 0 (контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример 1.5.16. Пусть дан произвольный алфавит

Тогда язык является праволинейным, так как он порождается грамматикой

Два наиболее распространенных способа конечного задания формального языка - это грамматики и автоматы. Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. В этой лекции рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам. Более сильные вычислительные модели будут определены позже, в лекциях "10", "14" и "15". Термин "автоматный язык" закреплен за языками, распознаваемыми именно конечными автоматами, а не какими-либо более широкими семействами автоматов (например, автоматами с магазинной памятью или линейно ограниченными автоматами).

В разделе 2.1 определяются понятия конечного автомата (для ясности такой автомат можно называть недетерминированным конечным автоматом) и распознаваемого конечным автоматом языка. В следующем разделе дается другое, но эквивалентное первому определение языка, распознаваемого конечным автоматом. Оно не является необходимым для дальнейшего изложения, но именно это определение поддается обобщению на случаи автоматов других типов.

В разделе 2.3 доказывается, что тот же класс автоматных языков можно получить, используя лишь конечные автоматы специального вида (они читают на каждом такте ровно один символ и имеют ровно одно начальное состояние). Во многих учебниках конечными автоматами называют именно такие автоматы.

Целую серию классических результатов теории формальных языков составляют теоремы о точном соответствии некоторых классов грамматик некоторым классам автоматов. Первая теорема из этой серии, утверждающая, что праволинейные грамматики порождают в точности автоматные языки, доказывается в разделе 2.4.

Другая серия результатов связана с возможностью сузить некоторый класс грамматик, не изменив при этом класс порождаемых ими языков. Обычно в таком случае грамматики из меньшего класса называются грамматиками в нормальной форме. В разделе 2.5^* формулируется результат такого типа для праволинейных грамматик. Сама эта теорема не представляет большого интереса, но аналогичные результаты, доказываемые позже для контекстно-свободных грамматик, используются во многих доказательствах и алгоритмах.

Не все конечные автоматы подходят для конструирования распознающих устройств, пригодных для практических приложений, так как в общем случае конечный автомат не дает точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Этого недостатка нет у детерминированных конечных автоматов (частного случая недетерминированных конечных автоматов), определенных в разделе 2.6. В разделе 2.7 доказывается, что каждый автоматный язык задается некоторым детерминированным конечным автоматом.

Примеры неавтоматных языков

Пример 3.4.1. Рассмотрим язык над алфавитом . Утверждение леммы 3.3.1 не выполняется ни для какого натурального числа p. Действительно, если w = ab^pa^p, то x = ab^k, y = b^m, z = b^p-k-ma^p для некоторых и или , y = ab^l, z = b^p-la^p для некоторого . В обоих случаях . Таким образом, язык L не является автоматным.

Замечание 3.4.3. Условие, сформулированное в лемме 3.3.1, является необходимым для автоматности, но не достаточным.

Пример 3.4.4. Пусть . Рассмотрим язык L = {a^kb^maⁿ | k=0 или m=n}. Положим p = 1. Тогда для любого слова длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Тем не менее язык L не является автоматным, так как

Лемма 3.4.5*. Пусть L - автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова можно подобрать слова , для которых верно xyz = w, и для всех . Здесь [m] означает целую часть числа m.

Доказательство. Пусть L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути . Обозначим l = [|w|/p]. Если l = 0, то положим и . Пусть . Согласно принципу Дирихле найдутся такие натуральные числа j и k, что и q_jl = q_kl. Выберем слова x, y и z так, что |x| = jl, |y| = kl - jl и xyz = w.

Эта лекция содержит дополнительные результаты, не используемые в дальнейшем изложении. В начале лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза.

В разделе 4.2* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.

В последнем разделе этой лекции устанавливается числовой критерий автоматности для языков над однобуквенным алфавитом (в терминах арифметических прогрессий) и доказывается связанное с длинами слов необходимое условие автоматности (для произвольного алфавита).

Теорема Клини

Определение 5.3.1. Назовем обобщенным конечным автоматом аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями. Метка пути такого автомата - произведение регулярных выражений на переходах данного пути. Слово w допускается обобщенным конечным автоматом, если оно принадлежит языку, задаваемому меткой некоторого успешного пути.

Замечание 5.3.2. Каждый конечный автомат можно преобразовать в обобщенный конечный автомат, допускающий те же слова. Для этого достаточно заменить всюду в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв.

Замечание 5.3.3. Если к обобщенному конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов не изменится.

Пример 5.3.4. Пусть . Обобщенный конечный автомат , где Q = {1,2,3}, I = {1,2}, F = {3},

допускает все слова в алфавите , кроме слов, содержащих подслово aa.

Теорема 5.3.5 (теорема Клини). Язык L является регулярным тогда и только тогда, когда он является автоматным.

Доказательство. Пусть e - регулярное выражение. Индукцией по построению e легко показать, что задаваемый им язык является автоматным (см. теорему 3.1.1).

Обратно, пусть язык L распознается некоторым (недетерминированным) конечным автоматом с одним начальным состоянием и одним заключительным состоянием. Существует эквивалентный ему обобщенный конечный автомат , где . Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными), заменим их на один переход, используя операцию +.

Устраним по очереди все состояния, кроме q₁ и q₂. При устранении состояния q нужно для каждого перехода вида , где , и для каждого перехода вида , где , добавить переход , где регулярное выражение g - метка перехода из q в q (если нет перехода из q в q, то надо добавить переход ), и снова всюду заменить параллельные переходы на один переход, используя операцию +.

После устранения всех состояний, кроме q₁ и q₂, получится обобщенный конечный автомат , где

Очевидно, что .

Пример 5.3.6. Рассмотрим язык, распознаваемый конечным автоматом

где и

Тот же язык порождается обобщенным конечным автоматом

где

После устранения состояния q₃ получается обобщенный конечный автомат

где

Можно упростить регулярные выражения и получить

После устранения состояния q₄ и упрощения регулярных выражений получается обобщенный конечный автомат

где

Следовательно, язык L(M) задается регулярным выражением

Упростив это регулярное выражение, получим

5.4*. Звездная высота

Определение 5.4.1. Звездная высота (star-height) регулярного выражения (обозначение sh(e)) определяется рекурсивно следующим образом:

Пример 5.4.2. Пусть . Тогда

sh((a^*+b^*+ab)^*+(ab^*c)^*) = 2.

Определение 5.4.3. Звездной высотой регулярного языка L (обозначение sh(L)) называется минимум звездных высот регулярных выражений, задающих этот язык.

Замечание 5.4.4. Регулярный язык L является конечным тогда и только тогда, когда sh(L) = 0.

Теорема 5.4.5. Пусть . Тогда для любого существует такой регулярный язык , что sh(L) = n.

Доказательство можно найти в книге Саломаа А. Жемчужины теории формальных языков. - М.: Мир, 1986 с.41-46.

Пример 5.4.6. Пусть и

Тогда sh(L) = 2. Действительно, язык L задается регулярным выражением (ab+ba+(aa+bb)(ab+ba)^*(aa+bb))^* и не задается никаким регулярным выражением меньшей звездной высоты.

Замечание 5.4.7. Неизвестно, верен ли аналог теоремы 5.4.5 для обобщенных регулярных выражений, в которых, помимо итерации, конкатенации и объединения, разрешена операция дополнения.

 

 

Основная цель данной лекции - доказать еще один критерий автоматности формального языка. Этот критерий можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости (однако формальные определения будут даны без использования понятия класса эквивалентности). Слова x и y считаются взаимозаменяемыми (относительно языка L), если при замене в любом слове из языка L подслова, совпадающего с x, на y снова получится слово из языка L и наоборот. В разделе 6.3 фактически доказывается, что язык L является автоматным тогда и только тогда, когда соответствующее отношение взаимозаменяемости разбивает множество всех слов рассматриваемого алфавита на конечное число классов эквивалентности.

Но сначала мы докажем аналогичный результат для отношения взаимозаменяемости не подслов, а префиксов (раздел 6.1). Соответствующие классы эквивалентности слов позволяют построить минимальный детерминированный конечный автомат для заданного языка. Известен и другой метод нахождения минимального детерминированного конечного автомата (раздел 6.2), но этот метод можно применять только тогда, когда уже имеется какой-нибудь детерминированный конечный автомат, распознающий данный язык. В конце лекции доказывается, что классы эквивалентности по взаимозаменяемости относительно автоматного языка сами являются автоматными языками.

Множества правых контекстов

Определение 6.1.1. Пусть и . Тогда множество правых контекстов слова y относительно языка Lопределяется следующим образом:

Пример 6.1.2. Пусть и . Тогда

1.

2. если , то ;

3. если , то ;

4. если , то .

Определение 6.1.3. Для любого состояния p полного детерминированного конечного автомата и любого слова w обозначим через такое состояние q, что существует путь из p в q с меткой w (в силу полноты и детерминированности такое состояние существует и единственно).

Лемма 6.1.4. Если язык L распознается полным детерминированным конечным автоматом , то

Доказательство. Пусть I = {s}. Введем обозначение

Определим функцию , положив f(A) равным , где y - некоторое слово, для которого выполнено условие (если существует несколько таких слов y, то можно использовать, например, первое среди них в лексикографическом порядке).

Заметим, что для любых слов u и v, если , то . Следовательно, функция f является инъективной. Но тогда .

Пример 6.1.5. Рассмотрим язык L, порождаемый полным детерминированным конечным автоматом из примера 2.6.4. Тогда

Лемма 6.1.6. Если и множество конечно, то язык L является автоматным.

Доказательство. Язык L распознается полным детерминированным конечным автоматом , где

Пример 6.1.7. Пусть . Рассмотрим автоматный язык L = a⁺b^*. Обозначим