fl_task4 (1178891)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Задание 4Замкнутость регулярных языков, теоремаМайхилла-Нероуда и минимальные автоматыКлючевые слова1 :язык, регулярный язык, ДКА, полный ДКА, НКА,отношение эквивалентности, декартово произведение.0ЛикбезЗадачи помеченные † не являются сложными, однако являются вкакой-то мере дополнительными. Я рекомендую их решать, но жёсткоэтого не требую.0.1Отношение эквивалентности(Бинарным) отношением R на множестве X называется некотороеподмножество R множества X × X. Говорят, что пара элементов x иy удовлетворяют отношению R, если пара (x, y) принадлежит R. Этопринято обозначать xRy.Отношение R называется рефлексивным, если для любого x ∈ X справедливо xRx. Отношение называется симметричным, если из факта xRyследует yRx.

Отношение называется транзитивным, если из xRy и yRzследует xRz.Определение 1. Бинарное отношение называется отношением эквивалентности, если оно является рефлексивным, симметричным и транзитивным. Такие отношения обычно обозначаются ∼R или просто ∼, когдаясно о каком отношении идёт речь.Классом эквивалентности C(x) называется множество элементов эквивалентных x. То есть C(x) = {y | x ∼ y}.Упражнение 1. Показать, что классы эквивалентности C(x) и C(y)либо не пересекаются, либо совпадают.1минимальный необходимый объем понятий и навыков по этому разделу)1Множество X, над которым задано отношение эквивалентности ∼,можно представить в виде объединения попарно непересекающихся множеств – классов эквивалентности, то есть факторизовать по отношению эквивалентности.

Фактормножество обозначается как X\∼ . То есть,X\∼ = {C(x) | x ∈ X}. Мощность фактормножества называется индексом отношения эквивалентности.0.2МорфизмыОпределение 2. Морфизмом называется отображение ϕ : Σ∗ → ∆∗ ,для которого справедливо: если w = uv, то ϕ(w) = ϕ(u) · ϕ(v).Операция взятия морфизма переносится на множества естественнымобразом: ϕ(X) = {ϕ(x) | x ∈ X}.Морфизм является частным случаем понятия гомоморфизма, которое вы изучали в рамках курса высшей алгебры. В современной терминологии гомоморфизмы также называют просто морфизмами.Упражнение 2.

Показать, что морфизм ϕ однозначно определён, еслидля каждой буквы σ алфавита Σ определено значение ϕ(σ).†Задача 1 . Доказать, что регулярные языки замкнуты относительновзятия морфизма.Определение 3. Обратным морфизмом ϕ−1 к морфизму ϕ : Σ∗ → ∆∗ ,называется отображение ϕ−1 (w) = {v | ϕ(v) = w}Морфизмы применяются не только к словам, но и к языкам. Записьϕ(L) означает, что ϕ(L) = {ϕ(w) | w ∈ L}, то же самое относится и кобратному морфизму: ϕ−1 (L) = {w | ϕ(w) ∈ L}.†Задача 2 . Верно ли, что для любого языка L и любого морфизмаϕ : Σ∗ → Σ∗1.

язык ϕ(ϕ−1 (L)) совпадает с L?2. язык ϕ−1 (ϕ(L)) совпадает с L??3. ϕ(ϕ−1 (L)) = ϕ−1 (ϕ(L))†Задача 3 . Доказать, что регулярные языки замкнуты относительнооперации взятия обратного морфизма.21Теорема Майхилла-НероудаПоскольку мы работаем со словами, то нас будут интересовать бинарные отношения на множестве Σ∗ . А именно, нас будет интересоватьследующее отношение эквивалентности, задаваемые языком L. Слово xL-эквивалентно слову y, если для любого суффикса z, слова xz и yz либоодновременно лежат в L, либо одновременно не принадлежат L.

Обратите внимание, что отношение эквивалентности задано на множестве всехслов Σ∗ , а не только на словах языка L: таким образом, x и y в определении – произвольные слова. Формально, x ∼L y ⇐⇒ ∀z ∈ Σ∗ : xz ∈L ⇔ yz ∈ L. Это отношение эквивалентности называется отношениемМайхилла-Нероуда.Легко видеть, что это отношение является правоинвариантным, тоесть если x ∼L y, то xz ∼L yz для любого z.Теорема 1 (Майхилл-Нероуд, 1958). Язык L является регулярным тогда и только тогда, когда Σ∗ разбивается на конечное число классовэквивалентности по отношению ∼L . Другими словами, когда ∼L – отношение конечного индекса.Доказательство. Если язык L регулярен, то отношение ∼L очевидноимеет конечный индекс. Действительно, возьмём произвольный полный2ДКА A, распознающий L, в котором все состояния достижимы3 .

Пусть Aимеет n состояний. Рассмотрим слова x1 , x2 , . . . , xn , такие что δ(q0 , xi ) =qi . По любому слову w автомат переходит из начального состояния внекоторое состояние qi , а значит w ∈ C(xi ), потому что для любого слова z, состояние q = δ(qi , z) либо принимающие, либо нет, а δ(q0 , xi z) =δ(q0 , wz) = δ(qi , z) = q, поэтому w ∼L xi . Таким образом, мощностьфактормножества Σ∗ \∼L не превосходит n, а значит самих классов эквивалентности конечное число.В обратную сторону. Пусть таких классов конечное число. Тогда,∗Σ \∼L = {C1 , C2 , .

. . , Cn }. Построим, имея такое разбиение, ДКА A, распознающий L.Построение: Можеством состояний является фактормножество, то есть2ДКА является полным, если в нём определены все переходы, т.е. ∀q ∈ Q, ∀σ ∈Σ : δ(q, σ) 6= ∅.3формально в Q могут быть состояния, в которые невозможно попасть из q0 . Обратите внимание, что они могут возникать при применении конструкции произведения,которая возникнет на следующем семинаре.3Q = Σ∗ \∼L , в качестве начального состояния q0 возьмём C(ε).

Функциюпереходов δ определим следующим образом. Пусть xi – представителькласса Ci , тогда δ(Ci , σ) = Cj , если xi σ ∈ Cj . Осталось описать множество принимающих состояний: F = {Ci | xi ∈ L}.Корректность: По построению, автомат A при обработке слова w наi-ом шаге оказывается в состоянии4 C(w[1, i]). Таким образом, обработавслово, автомат перейдёт в состояние C(w), которое будет принимающимтогда и только тогда, когда w ∈ L, поскольку если xi ∼L w, и слово xi лежит в языке L, то и слово w тогда лежит в языке L, иначе различающимдля них будет пустое слово.Эта теорема очень часто вызывает непонимание: почему мы можемпостроить автомат, если существует конечное разбиение. Да, допустим,что разбиение есть, но кто же нам его дал? При доказательстве теорем,мы можем использовать факты из логики вида «утверждение всегда либо истинно, либо ложно» и используем оракул, который отвечает на нашивопросы – если Оракул ответил «истинно», то мы начинаем одну ветвьрассуждений, если «ложно», то другую.

Если во всех ветках ответа оракула, мы доказали правильность нашего утверждения, то утверждениесчитается доказанным. Так, мы пользовались тем, что оракул сообщалнам конечное ли у нас число классов эквивалентности или нет, лежатли два слова в одном классе эквивалентности или нет и мы успешно построили автомат в доказательстве – это означает, что мы доказали, чтоесли классов эквивалентности конечное число, то такой автомат есть.На практике же, зная только то, что классов эквивалентности конечноечисло, автомат мы можем и не построить – для того, чтобы построить автомат, оракул должен быть вычислимой функцией, то есть мы должныуметь строить такую машину Тьюринга5 , которая отвечала бы на наши вопросы. Доказательства, в которых оракул вычислим, называютсяконструктивными.4Напомним, что w[i, j] есть подслово слова w, начинающееся с i-го символа w изаканчивающееся j-ым.5Или, например, мы можем написать программу на языке C.42Построение минимального автоматаДКА A называется минимальным автоматом, распознающим языкL, если L(A) = L и не существует ДКА B, такого что L(B) = L и числосостояний автомата B меньше числа состояний автомата A.Для доказательства существования и корректности построения минимального автомата мы будем использовать теорему Майхилла-Нероуда.Нам потребуется аналогичное отношению М.Н.

отношение эквивалентноwсти, определённое на состояниях. Будем использовать обозначение q −→p, если из состояния q обрабатывая слово w, автомат переходит в состояние p или что то же самое (q, w) `∗ (p, ε).Определение 4. Зафиксируем автомат A, распознающий язык L. Пустьxjxi→q i , а q0 −→ qj . Тогда qi ∼L qj тогда и только тогда, когда xi ∼L xj .q0 −Данное отношение мы назовём соответствующим отношению МайхиллаНероуда.Обратите внимание, что это два разных отношения эквивалентности,потому что одно из них определено на множестве всех слов, а другое намножестве состояний.

Мы обозначаем одинаково два разных отношения,потому что они схожи, но определены на разных объектах, поэтому этоне приведёт к путанице.Теорема 2. Для каждого регулярного языка, существует минимальный полный автомат, распознающий его. Состояния минимального автомата соответствуют классам эквивалентности по отношению МайхиллаНероуда ∼LДоказательство.

В силу теоремы Майхилла-Нероуда, язык L регулярентогда и только тогда, когда отношение ∼L имеет конечный индекс. Рассмотрим автомат A, построенный в доказательстве теоремы МайхиллаНероуда и покажем, что он является минимальным. Допустим противное – пусть автомат B имеет меньшее число состояний, чем A. Тогда,по принципу Дирихле, существует два слова xi и xj , такие что xi 6∼L xjxjxiи в автомате B при этом q0 −→q и q0 −→ q. Так как xi 6∼L xj , то найдётся такое слово z, что xi z ∈ L, а xj z 6∈ L. Но тогда с одной стороныzzq →− qf ∈ F , т.к. xi z ∈ L, а с другой стороны q →− qf¯ 6∈ F , посколькуxj z 6∈ L – приходим к противоречию.5Просто из факта того, что язык L имеет конечное число классов эквивалентности М.-Н., не совсем ясно как построить автомат A, распознающий L. Однако, имея любой ДКА, распознающий L можно конструктивно построить по нему минимальный автомат.

Рассмотрим регулярный язык L и распознающий его полный ДКА A. Идея построения поавтомату A минимального состоит в склейке эквивалентных состояний.Под склейкой состояний qi ∼L qj мы понимаем удаление состояния qj изавтомата A и направление всех переходов ведущих в него в состояние qi .Утверждение 1.

Склеив все эквивалентные состояния автомата A,мы получим минимальный автомат.Доказательство. Склейка состояний qi ∼L qj не изменит язык L(A),потому что из состояния qj по слову z, автомат A попадает в принимающее состояние тогда и только тогда, когда он попадает в принимающеесостояние по слову z из состояния qi . Таким образом, склеив все эквивалентные состояния автомата A, мы получим минимальный автомат,потому что в силу определения эквивалентности на состояниях каждоесостояние соответствует классу эквивалентности М.-Н. и по теореме 2,он является минимальным.Осталось привести алгоритм склейки состояний.Алгоритм. На вход алгоритма подаётся ДКА A.1.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов курсовой работы