Задание 2

Задание 2НКА и алгоритмы поиска подстрокЛитература:1. Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений.М.: Вильямс, 2002.2. Ахо А., Ульман Д.Теория синтаксического анализа, перевода и компиляцииМ.: Мир, 1978. Гл. 0, 2.3. Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.Теория и реализация языков программирования.М.: МЗ-пресс, 2006.4. Шень.

А. Х.Программирование: теоремы и задачиМ.: МЦНМО, 2004.5. Журавлёв Ю.И., Флёров Ю.А, Вялый М.Н.Дискретный Анализ. Формальные системы и алгоритмы.М.: МЗ-пресс, 2010.Ключевые слова1 : язык, регулярные выражения, конкатенация,объединение, итерация, конечные автоматы (КА), детерминированныеи недетерминированные КА, регулярные языки.Упражнения из этого задания не обязательно техать и присылать:они не оцениваются. Их стоит техать, если вы хотите получить обратнуюсвязь. Задачи, помеченные звёздочкой, являются необязательными, ноих решение сильно поощряется бонусными очками.1Построение по регулярному выражению конечного автоматаНа семинаре мы разобрали алгоритм построения детерминированногоконечного автомата по регулярному выражению. Однако, его нельзя на1минимальный необходимый объём понятий и навыков по этому разделу)1звать простым.

Построить недетерминированный автомат по регулярному выражению гораздо проще. В каком-то смысле, если вы имеете делос регулярным выражением, вы имеете дело с НКА.Напомним, что помимо обычных переходов недетерминированные автоматы, имеют также ε-переходы, т.е. переходы вида δ(qi , ε) = qj . Наличие таких переходов означает, что попав в состояние qi , автомат можетперейти в состояние qj не обрабатывая следующий символ слова.Пример 1.1q0q1ε0Легко видеть, что данный автомат принимает язык, состоящий изслов, оканчивающихся на 1.

При прочтении 1, автомат переходит из состояния q0 в q1 , дальше, если во входном слове ещё остались необработанные символы, автомат делает ε-переход из состояния q1 в q0 и продолжаетобработку слова.Для построения НКА по РВ будем использовать определение регулярного языка. Напомним определение класса регулярных языков REG.• ∅ ∈ REG.• ∀σ ∈ Σ : {σ} ∈ REG.• ∀X, Y ∈ REG : X · Y, X|Y, X ∗ ∈ REG.• Больше нет регулярных языков.Мы будем строить НКА по РВ из каждого пункта данного определения. С первыми двумя пунктами проблем нет – их я оставляю как лёгкоеупражнение.

Перейдём сразу к третьему пункту. Допустим уже построены автоматы A и B для регулярных языков X и Y соответственно. Мыбудем предполагать, что оба автомата имеют всего одно принимающеесостояние. Если в автомате несколько принимающих состояний, то можно построить эквивалентный ему автомат с единственным принимающим2состоянием, добавив к множеству состояний состояние qF , которое будетединственным принимающим, и добавив ε-переходы в qF из старого множества F : ∀q ∈ F : δ(q, ε) = qF . Будем схематично обозначать автоматыэллипсами, и помечать в них только начальное и принимающее состояние. Таким образом, автомат A имеет видq0AqFВ дальнейшем, мы будем предполагать, что начальное состояние насхеме находится слева, а принимающее справа.

Построим явно автоматраспознающий X · Y , L(A) = X, L(B) = Y .q0AAqFBBДля этого по автомату A распознающему язык X и автомату B, распознающему язык Y мы строим автомат, распознающий X · Y объединяямножеcтва состояний A и B так, что q0 = q0A , qFA = q0B , F = {qFB }. Опятьполучили автомат с единственным принимающим состоянием.Упражнение 1. Доказать, что построенный автомат распознаёт языкX ·Y.Для построения языка X|Y используем следующую конструкцию:q0AεAqFAεq0qFεεq0BB3qFBУпражнение 2. Доказать, что построенный автомат распознаёт языкX|Y .И наконец перейдём к построению автомата для языка X ∗ :εεq0εq0AεqFAqFAУпражнение 3.

Доказать, что построенный автомат распознаёт языкX ∗.Задача 1. Постройте НКА по регулярному выражению a((a|b)a)∗ .Задача 2.ДКА.2Постройте по НКА, полученному в предыдущей задачи,Распознавание текстовС помощью НКА можно легко описать язык, в который входят все слова,содержащие в качестве подслова некоторое слово. Например, следующийавтомат распознаёт слова, содержащие подслово ababa.a, ba, bq0Задача 3.ДКА.aq1bq2aq3bq4aq5Постройте по НКА, полученному в предыдущей задачи,Задача 4∗ . Докажите, что при построении ДКА по НКА данного вида(Σ∗ wΣ∗ ), число состояний ДКА не превосходит |w|.4Задача 5. Постройте НКА, распознающий слова, в которых есть хотябы одно из подслов abab, abb, abaa.Задача 6∗ . Постройте по НКА из предыдущей задачи ДКА. Что можносказать об оценке числа состояний для ДКА?3О построении ДКА по РВНа семинаре мы изучили алгоритм построения ДКА по РВ.

На первомэтапе мы строили дерево и вычисляли значения атрибутов firstpos, lastposи nullable. Принцип вычисления этих атрибутов состоит в том, что имеязначение атрибутов в дочерних узлах, мы можем вычислить атрибутысамого узла. Например для узла•fβ β F lβfα αT lαатрибуты узла • будутfα ∪ fβ •F lβfβ β F lβfα αT lαпотому что регулярное выражение α · β порождает слово w = uv, такоечто РВ α порождает u, РВ β порождает v, при этом слово u может бытьпустым, а слово v – нет. Отсюда, если u 6= ε, то w начинается с тех жесимволов, что и u, а значит fα ⊆ f• , а если u = ε, то w начинается с тех жесимволов, что и слово v, поэтому fβ ⊆ f• , отсюда f• = fα ∪ fβ .

Посколькуслово w имеет непустой суффикс v, порождённый fβ , то l• = lβ .Упражнение 4. Найти алгоритм вычисления атрибутов во всех остальных случаев для узлов с операциями • и |. Если не получается придуматьалгоритм, его можно найти в книге Серебрякова. Доказать корректностьвычисления атрибутов.5Задача 7∗ .

Мы рассматривали алгоритм построения ДКА по РВ, вкотором не встречается пустое слово. В случае когда оно встречается,исходное РВ R может быть преобразовано либо в выражение R0 , либо ввыражение R0 | ε, где в выражение R0 пустое слово уже не входит. Предложите алгоритм, который осуществляет такое преобразование.Задача 8∗ . Мы рассматривали алгоритм построения ДКА по РВ, вкотором не встречается пустое множество. В случае когда оно встречается, исходное РВ R может быть преобразовано либо в выражение R0 ,либо в выражение R0 | ε, причём пустое множество и постое слово в выражение R0 не входят.

Предложите алгоритм, который осуществляет такоепреобразование.Указание: Введите новый атрибут в дерево.6.