WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Александр Охотин 10 октября 2018 г. Содержание 1 Минимизация DFA 1 2 Введение в формальные грамматики 6 2.1 Синтаксис языков....................... ...»

Теоретическая информатика III, осень 2018 г .

Минимизация DFA. Введение в формальные грамматики

Александр Охотин

10 октября 2018 г .

Содержание

1 Минимизация DFA 1

2 Введение в формальные грамматики 6

2.1 Синтаксис языков................................... 6

2.2 Синтаксис естественных языков........................... 7

2.3 Синтаксис языков программирования....................... 8

2.4 Языки представления данных............................ 10

2.5 Биологические данные в качестве языков..................... 10

2.6 Абстрактные языки.................................. 11 3 Определения грамматик 12

3.1 Определение через дерево разбора......................... 14 1 Минимизация DFA Задача нахождения DFA с наименьшим числом состояний, распознающего тот же язык, что и данный DFA: минимизация DFA. Будет показано, что минимальный DFA всегда единственен, а также приведён алгоритм для его построения .

Если для каждого состояния DFA рассмотреть множество всех строк, принимаемых, начиная из этого состояния, и если для двух состояний эти множества совпадают, то эти два состояния взаимозаменяемы, и их можно объединить в одно .

Обозначение: для DFA A = (, Q, q0,, F ) множество строк, принимаемых из состояния q Q: LA (q) = { w | (q, w) F } .

Лемма 1. Пусть в DFA A = (, Q, q0,, F ), начиная из двух состояний, q и q, принимается одно и то же множество строк: LA (q) = LA (q ), где q = q .

Пусть q = q0. Тогда автомат B = (, Q \ {q }, q0,, F \ {q }), полученный удалением q и перенаправлением всех переходов, ведущих в q, в состояние q, распознаёт тот же язык .

Если же эти множества не совпадают, то существует строка, принадлежащая одному из них и не принадлежащая другому разделяющая строка .

Краткое содержание лекций, прочитанных студентам 2-го курса СПбГУ, обучающимся по программе математика, в осеннем семестре 2018–2019 учебного года.

Страница курса:

http://users.math-cs.spbu.ru/~okhotin/teaching/tcs3_2018/ .

Лемма 2. Пусть L регулярный язык .

Если для двух строк u, v существует такая строка w, что одна из строк uw, vw принадлежит языку L, а другая не принадлежит, то во всяком DFA, распознающем L, состояния (q0, u) и (q0, v) должны быть различны .

Доказательство. Если такие два состояния совпадут, то автомат или примет обе строки uw, vw, или обе отвергнет .

С помощью этого нехитрого свойства, например, можно доказывать нижние оценки числа состояний DFA, распознающих данный язык .

Два DFA изоморфны, если между их множествами состояний есть взаимно однозначное отображение, сохраняющее переходы и сопоставляющее начальное состояние начальному и принимающие принимающим .

Теорема 1. Минимальный DFA для данного регулярного языка единственен с точностью до изоморфизма .

Доказательство. Пусть A = (, P, p0,, E) и B = (, Q, q0,, F ) два минимальных DFA, распознающие язык L .

Для всякого состояния первого автомата, p P, пусть up кратчайшая строка, по которой оно достижимо (если состояние недостижимо, его можно удалить, и тогда автомат не был бы минимальным). Тогда из состояния p принимается язык LA (p) = { v | up v L } .





В силу минимальности A, никакие два из этих языков не совпадают иначе их можно было бы объединить по лемме 1 .

По этой же строке up, автомат B достигает состояния qp, из которого принимается тот же самый язык LB (qp ) = { v | up v L }. Эти языки также попарно не совпадают. Тогда состоянию p ставится в соответствие состояние qp, и, в частности, p0 отображается в q0 .

Поскольку у B столько же состояний, сколько и у A, никаких других состояний у него нет, и получено взаимно однозначное соответствие между P и Q. Это соответствие сохраняет переходы: а именно, если p соответствует q, то состояния p = (p, a) и q = (q, a) также должны соответствовать друг другу. Действительно, из каждого из этих состояний должен приниматься язык { v | up av L }, и в каждом из автоматов есть только одно такое состояние .

–  –  –

Рис. 1: Разбиение класса R на три класса на основе переходов по символу a .

в разные классы, то пусть R = R1... Rk, где все переходы из Rj по a идут в один из существующих классов Rj. Тогда R заменяется на классы R1,..., Rk, как показано на рис. 1. Действительно, если классы Rj1 и Rj2 различаются по некоторой строке w, то Rj1 и Rj2 различаются по строке aw .

Алгоритм 1 Минимизация DFA .

Дано: DFA (, Q, q0,, F ) .

В каждый момент времени алгоритм помнит разбиение Q на классы эквивалентности R0,..., Rm1 .

–  –  –

Это повторяется, пока дальнейшее измельчение классов возможно. Когда далее измельчать становится некуда, строится новый автомат, состояниями которого станут построенные классы эквивалентности .

Теорема 2. Алгоритм 1, строит автомат, распознающий тот же язык, что и исходный, и минимальный среди всех автоматов, распознающих этот язык .

Алгоритм работает за время O(|| · n2 ), где n число состояний в исходном автомате, а алфавит .

–  –  –

(минимальность) Пусть p и q состояния исходного DFA, попадающие в разные классы эквивалентности. Утверждается, что есть строка, принимаемая из одного и отвергаемая из другого. Индукция по номеру шага алгоритма, на котором эти два состояния будут распределены в различные классы .

Базис: в разных классах с самого начала. Тогда одно из них принимающее, а другое отвергающее, и разделяющая строка .

Переход: пусть на каком-то шаге оба состояния p, q принадлежат некоторому классу R, рассматриваются переходы из R по a, и выясняется, что [(p, a)] = [(q, a)]. Тогда состояния (p, a) и (q, a) попали в различные классы ещё прежде, и потому, по предположению индукции, есть строка w, принимаемая из одного из них и не принимаемая из другого. Тогда строка aw разделяет p и q .

Отсюда, согласно лемме 2, классы [p] и [q] должны быть различными состояниями построенного автомата .

Время: O(|| · n2 ), так как число шагов измельчения O(n), и для каждого надо просмотреть O(n) состояний и вычислить переходы по каждому символу .

Пример 1. Автомат с 5 состояниями, приведённый на рис .

2, распознаёт язык { w | w {a, b}, |w|a 0 (mod 3) }, хотя с виду этого не скажешь. Но стоит его минимизировать, как всё становится ясно .

Алгоритм начинает с разбиения R0 = {1, 2, 4}, R1 = {0, 3}, приведённого на рис. 3(левом верхнем). Класс R1 разбить не удаётся ни по a, ни по b, а вот класс R0 разбивается по a, поскольку из состояний 1 и 4 переходы по a ведут в R0 же, а переход по a из состояния 2 уходит в R1. Поэтому R0 заменяется на R2 = {1, 4} и R3 = {2}, полученное разбиение дано на рис. 3(правом верхнем). Ничего больше разбить не удаётся, так что получается минимальный автомат с 3 состояниями на рис. 3(нижнем) .

–  –  –

Рис. 3: Минимизация автомата из примера 1: (сверху слева) начальное разбиение; (сверху справа) измельчённое разбиение; (снизу) соответствующий минимальный DFA .

–  –  –

Для задачи минимизации NFA полиномиальный по времени алгоритм неизвестен. Вычислительная сложность этой задачи будет рассмотрена далее в курсе .

Применение минимизации DFA к распознаванию свойств автоматов. Как проверить для двух DFA, задают ли они один и тот же язык? Сперва минимизировать оба .

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

Другая задача: проверить, задаёт ли данное регулярное выражение язык. Перевести в DFA с экспоненциальным ростом, минимизировать, и затем проверить, получился ли автомат с одним принимающим состоянием. Далее в курсе будет показано, что более эффективные алгоритмы неизвестны .

2 Введение в формальные грамматики Формальная грамматика математическая модель синтаксиса языков, как естественных (русский, и т.д.), так и искусственных (C++, XML и т.д.). С помощью формальных грамматик можно строго определить такие задачи, как разбор предложений по составу (как это делают в школе) .

2.1 Синтаксис языков

Общие черты синтаксиса языков:

1. представление информации в виде строки символов из некоторого алфавита;

2. не всякая символьная строка правильно построенное предложение, и синтаксис это принцип построения правильных предложений;

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

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

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

К ним прилипло странное название бесконтекстные грамматики (context-free; на птичьем языке контекстно-свободные ), возникшее в связи тогдашними попытками придумать модель грамматик, где задавались бы правила, применимые в отдельных контекстах. Плоды этих попыткок давно и безнадёжно устарели, но от них осталось сомнительное название для обыкновенных грамматик, мешающее правильно их понимать уже нескольким поколениям .

–  –  –

2.2 Синтаксис естественных языков Разбор предложения по составу: выделяются фразы, словосочетания, строится дерево разбора. В традиционных грамматиках описываются синтаксические категории и то, как они могут сочетаться. Например, английское предложение Every man is mortal разделяется на подлежащее с зависимыми словами Every man ( состав подлежащего ) и сказуемое с зависимыми словами is mortal ( состав сказуемого ). Американские лингвисты, такие как Блумфилд и Сапир, называли этот подход анализом непосредственных составляющих (immediate constituent analysis) .

Эти правила можно выразить в виде математического определения грамматически верных предложений, состоящего из высказываний вида Если вслед за любым составом подлежащего (noun phrase) записать любой состав сказуемого (verb phrase), то получится предложение. В обозначениях формальных грамматик это правило записывается так .

–  –  –

В таком виде правила грамматик были впервые записаны Хомским [1956] .

Рис. 6: Леонард Блумфилд (1887–1949), Эдвард Сапир (1884–1939), Ноам Хомский (род .

1928) .

Синтаксис естественных языков не столь упорядочен, чтобы совершенно точно описываться формальными грамматиками. Как остроумно заметил Сапир [1921], все грамматики подтекают ( all grammars leak ) и, несмотря на все последующие математические изыскания, грамматики продолжают подтекать и сегодня. Тем не менее, формальные грамматики остаются наилучшим математическим приближением синтаксиса естественных языков, и более точные модели в лингвистике получаются их уточнением .

2.3 Синтаксис языков программирования Алгол 60: первый научно разработанный язык программировани. Грамматики использовались в качестве средства определения синтаксиса. В программистской среде грамматики получили название BNF (Backus–Naur form, форма Бэкуса–Наура), в честь двух членов комитета разработчиков .

–  –  –

Арифметические выражения .

Пример 2 (Синтаксис арифметических выражений). Общематематическое определение .

• Переменная x арифметическое выражение .

• Число арифметическое выражение .

–  –  –

Ничто другое не является арифметическим выражением .

Для простоты. пусть x переменная, 1 число. Тогда x*(x+1) арифметическое выражение, а x*)1+ нет .

В виде формальной грамматики .

–  –  –

Здесь E синтаксическая категория арифметических выражений .

Операторы языка программирования while(x0) x=x+1;

Продолжение: логические выражения .

–  –  –

SGML, HTML, XML. Предельно упрощённый синтаксис, удобно для машинной обработки. По существу, это отказ от привычного синтаксиса языков в пользу явного задания дерева разбора: в самой строке записано, как её надо разбирать .

Пример 4. Определение маленького фрагмента HTML, с одной парой тэгов .

• Всякий символ, кроме угловых скобок (, ) правильная HTML-строка .

• Конкатенация двух правильных HTML-строк тоже правильная HTML-строка .

• Если x правильная HTML-строка, то blockquote x /blockquote тоже .

В виде формальной грамматики (символ c обозначает любой знак) .

–  –  –

2.5 Биологические данные в качестве языков Первичная структура РНК: цепочка сахаров, соединённых друг с другом через фосфаты, и к каждому присоединён один из четырёх нуклеотидов: G (гуанин), C (цитозин), A (адеописывается символьной строкой над алфавитом = {g, c, a, u} .

нин) или U (урацил) Молекула, изображённая на рис. 11, описывается строкой из 4 символов .

Вторичная структура: последовательность сгибается и соединяется сама с собою с помощью водородных связей, образуя соединения G–C (три связи) и A–U (две связи). На рис. 11 возможные соединения помечены стрелками, а пунктирные линии в верхней части рисунка показывают возможное сгибание этой 4-символьной последовательности .

Пример вторичной структуры: шпилька (hairpin) как на рис. 12(левый) .

Пример 5. Общее определение (с некоторыми погрешностями против биологии) .

• Всякая последовательность нуклеотидов это петля (loop) .

–  –  –

Рис. 11: Химическая формула молекулы РНК, содержащей последовательность gauc. Пунктирные линии: возможное сгибание молекулы, при котором соединяются g и c, а также a и u .

–  –  –

Пример дерева разбора: рис. 12(правый) .

2.6 Абстрактные языки Язык Дика множество правильно вложенных последовательностей скобок .

Пример 6. Общее определение .

–  –  –

3 Определения грамматик Определение 1. (Формальная) грамматика это четвёрка G = (, N, R, S), состоящая из следующих компонентов .

–  –  –

• Конечное множество N это множество определяемых в грамматике свойств строк, которым всякая строка над алфавитом обладает или не обладает. Обозначаются обычно буквами A, B, C,.. .

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

• Конечное множество R правил грамматики, каждое из которых описывает возможную структуру строк со свойством A N в виде конкатенации u0 B1 u1... B u, где B1,..., B ( 0) все нетерминальные символы, на которые ссылается правило,

–  –  –

Рис. 15: Дерево разбора строки abaabb по грамматике из примера 7 .

а любые символы, написанные между ними, образуют строки u0, u1,..., u .

–  –  –

• Начальный символ S N, от sentence, обозначает множество всех синтаксически правильных строк, определямых в грамматике .

Общий вид правил часто записывается как A X1... X, где X1,..., X N ( 0) все символы и нетерминальные символы, конкатенация которых записана в правиле .

Дальнейшее обозначение: A, где = X1... X строка над алфавитом N .

Несколько правил A 1,..., A m для одного и того же нетерминального символа A N записывают возможную структуру строк с этим свойством. Это такой же оператор выбора, как и в регулярных выражениях, и потому такие правила обычно записываются следующим образом .

A 1 |... | m Пример 7. Грамматика для языка Дика записывается как G = (, N, R, S), где = {a, b}, N = {S} и R = {S aSb, S SS, S }. Такую грамматику записывают следующим образом .

S aSb | SS | Дерево разбора строки w = abaabb в соответствии с этой грамматикой приведено на рис. 15 .

3.1 Определение через дерево разбора Дерево разбора это уже само по себе формальное определение .

Дерево разбора строки w. Потомки каждой внутренней вершины упорядочены, откуда вытекает порядок на листьях. Листья слева направо помечены символами строки w. Каждая внутренняя вершина помечена некоторым нетерминальным символом A N, и её потомки, то в грамматике должно быть правило A X1... X. Для если X1,..., X правила A вершина помечена символом A, не имеет потомков, но всё равно рассматривается в качестве внутренней .

Язык, задаваемый грамматикой, L(G), содержит все строки, для которых есть дерево разбора .

Другие определения на следующей лекции .

Список литературы [1956] N. Chomsky, “Three models for the description of language”, IRE Transactions on Information Theory, 2:3 (1956), 113–124 .

[1971] J. E. Hopcroft, “An n log n algorithm for minimizing states in a nite automaton”, Theory of Machines and Computations (Haifa, Israel, 16–19 August 1971), 189–196 .

[1921] E. Sapir, Language: An Introduction to the Study of Speech, 1921 .






Похожие работы:

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА И ПРОДОВОЛЬСТВИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ "ВИТЕБСКАЯ ОРДЕНА "ЗНАК ПОЧЕТА" ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ВЕТЕРИНАРНОЙ МЕДИЦИНЫ" Кафедра нормальной и патологической физиологии ОБЩАЯ НО...»

«Фармацевтический рынок РОССИИ Выпуск: ноябрь 2014 розничный аудит фармацевтического рынка РФ – ноябрь 2014 события фармацевтического рынка – декабрь 2014 Информация основана на данных розничного аудита фармацевтического рынка РФ DSM Group, система менеджмента качества которого соответствует т...»

«Молекулярные механизмы мышечного сокращения Николай Борисович Гусев План • Ультраструктура сократительного аппарата • Структура миозина II • Упаковка миозина в филаменты • Некоторые минорные белки миозинового филамента • Моторный домен миозина и современные представления о его функционировании • Классификация миозина....»

«ФЕДОРОВА ОКСАНА ИВАНОВНА ВЛИЯНИЕ ДОМЕСТИКАЦИИ НА ХОЗЯЙСТВЕННО ПОЛЕЗНЫЕ И МОРФОФИЗИОЛОГИЧЕСКИЕ ПРИЗНАКИ НОРКИ АМЕРИКАНСКОЙ (MUSTELA VISON SCHREBER, 1777), ХОРЬКА (MUSTELA PUTORIUS L., 175...»

«ВЕРНАДСКИЕ И РОССИЙСКАЯ ДИАСПОРА МЕЖДУНАРОДНАЯ НАУЧНАЯ КОНФЕРЕНЦИЯ Москва. 14–15 марта 2013 М.Ю. Сорокина МЕЖДУ СОВЕТСКОЙ МЕТРОПОЛИЕЙ И РОССИЙСКОЙ ДИАСПОРОЙ: НЕЮБИЛЕЙНЫЕ ЗАМЕТКИ О НАСЛЕДИИ СЕМЬИ ВЕРНАДСКИХ 14–15 марта 2013 г. в Д...»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ Министерство образования Иркутской области Рабочая программа по факультативу: "Анатомия человека" 8 класс 2015-2016 учебный год Составитель: Жданова Н.В., учитель биологии и химии ГОКУ "Санаторная школа-интернат № 4, первая квалификационная категория Усолье...»

«Фармацевтический рынок РОССИИ Выпуск: февраль 2015 розничный аудит фармацевтического рынка РФ – февраль 2015 события фармацевтического рынка – март 2015 Информация основана на данных розничного аудита фармацевтического рынка РФ DSM G...»

«ОСНОВНАЯ ПРОФЕССИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА ПОДГОТОВКИ БАКАЛАВРА по направлению 06.03.01 Биология профиль Общая биология Б. 1.13.3 Модуль Зоологический. Основы протистологии Приложение 1 Типовые задания для проведения процедур оценивания результатов освоения дисциплины в ходе текущего ко...»







 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.