Лекции по теории формальных языков

1 Лекции по теории формальных языков Лекция 2. Недетерминированные конечные автоматы. Операции над автоматными языками. Регулярные языки. Автоматные фрагменты языков программирования Александр Сергеевич Герасимов Кафедра математических и информационных технологий Санкт-Петербургского академического университета Российской академии наук. Весенний семестр 2010/11 учебного года 18 февраля 2011 г. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 1 / 35

2 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 2 / 35

3 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 3 / 35

4 Определение недетерминированного конечного автомата Недетерминированным конечным автоматом (НКА) называется пятёрка B = (Q, Σ, δ, Q 0, F), где Q непустое конечное множество состояний, Σ алфавит, δ : Q Σ 2 Q функция переходов, Q 0 Q множество начальных состояний, F Q множество заключительных (или допускающих) состояний. (δ может быть определено и как отношение δ Q Σ Q.) НКА, находящийся в состоянии q и обозревающий ячейку с символом a, может перейти в любое состояние из множества δ(q,a). А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 4 / 35

5 Язык, распознаваемый НКА Доопределим функцию переходов δ на Q Σ : δ(q, ε) = , δ(q, ua) = r δ(q,u) δ(r,a). НКА B = (Q, Σ, δ, Q 0, F) распознает (или допускает) цепочку w Σ, если δ(q, w) F. q Q 0 Множество всех цепочек, допускаемых автоматом B, называется языком, распознаваемым автоматом B, и обозначается L(B). А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 5 / 35

6 Задание НКА расширенной таблицей переходов НКА B: a b Q 0 F q 0 q 0,q 1 q q 1 q q 2 q 2 q А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 6 / 35

7 Задание НКА диаграммой переходов НКА B тот же, что и на предыдущем слайде. aab L(B): δ(q 0,a) = = δ(q 0,aa), δ(q 0,aab) = F. abba / L(B): δ(q 0,abba) = F =. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 7 / 35

8 Теорема Рабина-Скотта Теорема (Рабина-Скотта) Класс языков, распознаваемых НКА, совпадает с классом языков, распознаваемых ДКА. Д о к а з а т е л ь с т в о. ДКА является частным случаем НКА, поэтому класс языков, распознаваемых ДКА, содержится в классе языков, распознаваемых НКА. Докажем обратное включение. Пусть B = (Q, Σ, δ, Q 0, F) произвольный НКА. Возьмём ДКА A = (2 Q, Σ, δ, Q 0, F ), где δ (P,a) = q P δ(q,a), F =

, и докажем, что L(A) = L(B). А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 8 / 35

9 Теорема Рабина-Скотта: продолжение доказательства Индукцией по длине произвольной w Σ установим, что для любого P 2 Q δ (P, w) = δ(q, w). q P База индукции ( w = 0) верна, поскольку ( ) δ (P, ε) = P = q P δ(q, ε). Индукционный переход. Рассмотрим w = ua. δ (P, ua) = δ (δ (P, u),a) = инд. предп. δ δ(q, u), a = опр. δ q P δ(q, ua). r Ë q P δ(r,a) = δ(r,a) = δ(q,u) q P r δ(q,u) q P А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 9 / 35

10 Теорема Рабина-Скотта: окончание доказательства Наконец, пользуясь определениями и беря Q 0 в качестве P в ( ), получаем L(A) = = = = L(B). q Q 0 Применённый в доказательстве теоремы способ получения ДКА по НКА называется «построением подмножеств». А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 10 / 35

11 Алгоритм нахождения ДКА по НКА (построением подмножеств). Вход. НКА B = (Q, Σ, δ, Q 0, F). Выход. Эквивалентный ДКА A = (Q, Σ, δ, Q 0, F ) без недостижимых состояний. 1. для каждого P Q label(p) := 0; 2. Q := ; 3. пока ( P Q : label(p) = 0) повторять 4. для каждого a Σ 5. δ (P,a) := δ(q,a); q P 6. Q := Q ; 7. label(p) := 1; 8. F :=

Все состояния автомата A достижимы, поскольку каждое состояние в Q, кроме начального, получено переходом в него из ранее построенного состояния. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 11 / 35

12 Пример построения ДКА по НКА a b Q 0 F q 0 q 0,q 1 q q 1 q q 2 q 2 q a b F 0 0 1 1 А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 12 / 35

13 ε-нка может не сдвигаться по входной цепочке по окончании некоторых тактов (на таком такте автомат прочитывает ε). Диаграмма переходов ε-нка может содержать дуги, помеченные ε. ε-нка распознает цепочку w в диаграмме переходов существует путь из начального состояния в заключительное, помеченный w. (Определение распознаваемой цепочки через обобщение функции переходов будет дано ниже.) А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 13 / 35 Определение недетерминированного конечного автомата с ε-переходами Определяемые здесь автоматы будет удобно строить по заданным языкам. Недетерминированным конечным автоматом с ε-переходами (ε-нка) называется пятёрка B = (Q, Σ, δ, Q 0, F), где Q, Σ, Q 0, F те же, что и в случае НКА, δ : Q (Σ ) 2 Q функция переходов.

14 Нормальные ε-нка Произвольный ε-нка эквивалентен ε-нка с единственным начальным и единственным заключительным состоянием: добавим следующим образом к исходному автомату состояния q 0 и f и объявим множеством начальных состояний, а множеством заключительных состояний нового автомата. ε-нка вида (Q, Σ, δ, , ) будем называть нормальными. В дальнейшем мы рассматриваем только нормальные ε-нка. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 14 / 35

15 Цепочки, распознаваемые (нормальным) ε-нка Пусть B = (Q, Σ, δ, , ) (нормальный) ε-нка. Определим отношение ρ Q 2 : (q,p) ρ p δ(q, ε). (q,p) ρ (рефлексивно-транзитивное замыкание отношения ρ) автомат может перейти из состояния q в состояние p, не сдвигаясь по входной цепочке. Замыкание состояния q: Clo(q) =

. Замыкание множества состояний P Q: Clo(P) = q P Clo(q). Обобщённая функция переходов δ : Q Σ 2 Q, δ(q, ε) = Clo(q), δ(q, ua) = Clo(δ(r,a)). r δ(q,u) r δ(q, w) в диаграмме переходов автомата B существует путь из q в r, помеченный w. Цепочка w распознаётся автоматом B, если f δ(q 0, w). А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 15 / 35

16 Теорема Класс языков, распознаваемых ε-нка, совпадает с классом языков, распознаваемых НКА. Д о к а з а т е л ь с т в о. Пусть B = (Q, Σ, δ, , ) (нормальный) ε-нка. Определим НКА B = (Q, Σ, δ, Q 0, ), где Q 0 = Clo(q 0 ), δ (q,a) = δ(q,a). Пути, помеченные цепочкой w Σ, в диаграммах переходов B и B существуют или не существуют одновременно: Таким образом, множества цепочек, распознаваемых B и B, совпадают. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 16 / 35

17 Алгоритм нахождения ДКА по ε-нка Вход. ε-нка B = (Q, Σ, δ, , F). Выход. Эквивалентный ДКА A = (Q, Σ, δ, Q 0, F ) без недостижимых состояний. 1. для каждого P Q label(p) := 0; 2. Q 0 := Clo(q 0 ); Q := ; 3. пока ( P Q : label(p) = 0) повторять 4. для каждого a Σ 5. δ (P,a) := δ(q,a); q P 6. Q := Q ; 7. label(p) := 1; 8. F :=

Это видоизменение алгоритма, описанного на слайде 11. Замыкание Clo(q) вычисляется поиском из состояния q. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 17 / 35

18 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 18 / 35

19 Определение автоматного языка. Теорема о замкнутости класса автоматных языков относительно некоторых операций Назовём язык автоматным, если он распознаётся некоторым конечным автоматом (каким?). Обозначим через A класс всех автоматных языков. Теорема Класс A замкнут относительно объединения, пересечения, дополнения, произведения и итерации. Д о к а з а т е л ь с т в о. Замкнутость относительно объединения. Пусть B 1 = (Q 1, Σ, δ 1, , ) и B 2 = (Q 2, Σ, δ 2, , ) нормальные ε-нка, Q 1 Q 2 =. Тогда язык L(B 1 ) L(B 2 ) распознаётся следующим нормальным ε-нка (Q 1 Q 2 , Σ, δ 3, , ): А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 19 / 35

20 Теорема: продолжение доказательства Замкнутость относительно произведения. L(B 1 )L(B 2 ) Замкнутость относительно итерации. L(B 1 ) А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 20 / 35

21 Теорема: окончание доказательства Замкнутость относительно дополнения. Пусть A = (Q, Σ, δ,q 0, F) (полный) ДКА. Тогда язык L(A) распознаётся ДКА (Q, Σ, δ,q 0, Q \ F). Замкнутость относительно пересечения. K L = K L А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 21 / 35

23 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 23 / 35

25 Теорема Клини: продолжение доказательства База индукции. Функция переходов δ нигде не определена. Тогда L(A) = , если q 0 F, и L(A) = иначе. Существует ровно один переход δ(q,a) = r. Если q q 0, то имеем: L(A) = при q 0 F, а иначе L(A) =. Разберём все возможные случаи, если q = q 0 : r = q 0 q F r F L(A) нет нет нет нет нет да нет да нет нет да да да нет нет да да да А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 25 / 35

26 Теорема Клини: продолжение доказательства Индукционый переход. Пусть автомат A = (Q, Σ, δ,q 0, F) имеет k > 1 переходов. Зафиксируем один переход δ(q,a) = r. Через δ обозначим (частичную) функцию переходов на Q Σ такую, что значение δ не определено на паре (q,a) и совпадает со значением δ на всех остальных парах. Рассмотрим автоматы A 0 = (Q, Σ, δ,q 0, F), A 1 = (Q, Σ, δ,q 0, ), A 2 = (Q, Σ, δ,r, ), A 3 = (Q, Σ, δ,r, F), каждый из которых имеет (k 1) переход. По индукционному предположению языки L(A 0 ), L(A 1 ), L(A 2 ), L(A 3 ) регулярны. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 26 / 35

29 Построение конечного автомата по регулярному выражению Нормальный ε-нка, распознающий язык a(a b) ab: А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 29 / 35

30 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 30 / 35

31 Регулярные выражения, задающие идентификаторы и числа Имя (или идентификатор): Целое без знака: Число без знака: имя = буква ( буква цифра ), где буква = a b. z, цифра = целое_без_знака = цифра ( цифра ) число_без_знака = целое_без_знака (. целое_без_знака ε) (E(+ ε) целое_без_знака ε) А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 31 / 35

32 Регулярные выражения, задающие константы и простые типы Константа (в языке Паскаль): константа = ((+ ε) число_без_знака имя ) ( буква цифра ) Простой тип (в языке Паскаль): простой_тип = имя ( имя (, имя ) ) константа.. константа Арифметические выражения (со сбалансированными скобками) не задаются регулярными выражениями, иначе говоря, не распознаются конечными автоматами. А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 32 / 35

33 План 1 Недетерминированные конечные автоматы 2 Операции над автоматными языками 3 Регулярные языки 4 Автоматные (регулярные) фрагменты языков программирования 5 Пример нерегулярного языка А. С. Герасимов (СПбАУ РАН) Лекции по теории формальных языков 18 февраля 2011 г. 33 / 35

34 Нерегулярность скобочного языка LB Предположим, что язык LB распознаётся некоторым ДКА A. Пусть n число состояний этого автомата. Автомат A распознаёт цепочку w = [[. [ ]. ]]. > S 0101 10S01 б) L(G)= u

Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика и теория алгоритмов, осень 2017 Семинар 1: язык записи формальных утверждений Алфавитом называется

Тема 1-1: Введение. Метод математической индукции. Множества и операции над ними А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной

Математические методы верификации схем и программ Лекторы: Захаров Владимир Анатольевич Подымов Владислав Васильевич e-mail рассказчика: valdus@yandex.ru Осень 2017 Лекция 7 Задача model checking для LTL

LR-анализ А. А. Рубцов 3 декабря 2018 г. 1 Магазинный автомат для правого вывода Пусть G КС-грамматика. Опишем недетерминированный (расширенный) МП-автомат, допускающий по пустому стеку, который распознаёт

Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика и теория алгоритмов, осень 2018 Семинар 1: язык записи формальных утверждений, с решениями некоторых

69 Алгоритм построения НКА по праволинейной автоматной грамматике 1. Множество вершин НКА состоит из нетерминалов грамматики и, возможно, еще одной новой вершины F, которая объявляется заключительной.

Рабочая программа составлена на основании: 1) Государственного образовательного стандарта высшего профессионального образования по направлению подготовки 657100 (230400) «Прикладная матика» (регистрационный

7.1. Понятие конечного автомата Конечным автоматом Мили называется шестерка объектов: А = , где: S конечное непустое множество (состояний); X конечное непустое множество входных сигналов

ÃËÀÂÀ 4 Ñâîéñòâà ðåãóëÿðíûõ ÿçûêîâ В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков теорема, которая называется

Введение в математическую логику Лекция 11 В следующем разделе мы будем рассуждать в терминах содержательной теории множеств, а не в терминах формальной теории ZF. Полный порядок (содержательная теория

Машина Тьюринга 1 Машина Тьюринга математическое понятие, а не реальная вычислительная машина. MT является математической моделью вычислительного устройства. MT была предложена Аланом Тьюрингом в 1936

Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ Глава 1 ЯЗЫКИ ИХ ПРЕДСТАВЛЕНИЕ 1.1. Алфавиты и языки Приступая к изучению теории языков, прежде всего следует определить, что мы подразумеваем под термином язык. Энциклопедическое

Московский государственный университет им. М.В. Ломоносова Языки программирования 5. Конечные автоматы Разработчики: М.Л. Цымблер, к.ф.-м.н., доцент Н.С. Силкина Южно-Уральский государственный университет

ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК Порождающие грамматики служат для точного, формального задания языков. На практике часто ставится обратная задача: построить грамматику на основе некоторого числа примеров

Рекомендовано МССН «Информатика» ПРОГРАММА Наименование дисциплины Теория автоматов и формальных языков Рекомендуется для направления (ий) подготовки (специальности (ей)) 02.03.02 Фундаментальная информатика

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Озерский технологический институт филиал НИЯУ МИФИ Вл. Пономарев Конспективное изложение теории языков программирования и методов трансляции

Задание 10 КС-языки: замкнутость и LL-анализ Ключевые слова 1 :язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. 1 Лемма о накачке Одна из целей изучения леммы