Лекция Недетерминированные конечные автоматы. Операции над автоматными языками. Регулярные языки



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

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

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

:
δ(q, ε) = {q},
δ(q, ua) =
r∈δ
(q,u)
δ(r, a).
НКА B = (Q, Σ, δ, Q
0
, F ) распознает (или допускает) цепочку w
∈ Σ

, если, w )


F
= Множество всех цепочек, допускаемых автоматом B, называется языком, распознаваемым автоматом, и обозначается АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Задание НКА расширенной таблицей переходов
НКА B:
a b
Q
0
F
q
0
q
0
, q
1
q
0 1
0
q
1
q
2 0
0
q
2
q
2
q
1 АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Задание НКА диаграммой переходов
НКА B тот же, что и на предыдущем слайде L(B): δ(q
0
, a) = {q
0
, q
1
} = δ(q
0
, aa),
δ(q
0
, aab) = {q
0
, q
2
} ∩ F = ∅.
abba
/
∈ L(B): δ(q
0
, abba) = {q
0
, q
1
} ∩ F = АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема Рабина-Скотта
Теорема (Рабина-Скотта)
Класс языков, распознаваемых НКА, совпадает с классом языков,
распознаваемых ДКА.
Д ока за тел ь ст во. ДКА является частным случаем НКА,
поэтому класс языков, распознаваемых ДКА, содержится в классе языков, распознаваемых НКА. Докажем обратное включение.
Пусть B = (Q, Σ, δ, Q
0
, F ) — произвольный НКА.
Возьмём ДКА A = (2
Q
, Σ, δ , Q
0
, F ), где (P, a) =
q∈P
δ(q, a),
F
= {P ∈ 2
Q
| P ∩ F = и докажем, что L(A) = АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема Рабина-Скотта: продолжение доказательства
Индукцией по длине произвольной w ∈ установим, что для любого P ∈ 2
Q
δ (P, w ) =
q∈P
δ(q, w ).
( База индукции (|w | = 0) верна, поскольку (P, ε) = P =
q∈P
δ(q, Индукционный переход. Рассмотрим w = ua.
δ (P, ua) = δ (δ (P, u), a) инд. предп.
δ


q∈P
δ(q, u), a


=
опр. δ
r∈
Ë
q∈
P
δ
(q,u)
δ(r, a) =
q∈P r∈δ
(q,u)
δ(r, a) =
q∈P
δ(q, АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема Рабина-Скотта: окончание доказательства
Наконец, пользуясь определениями и беря в качестве P в ( получаем) = {w ∈ Σ

| δ (Q
0
, w ) ∈ F } =
{w ∈ Σ

| δ (Q
0
, w ) ∩ F = ∅} =
{w ∈ Σ

|
q∈Q
0
δ(q, w )
F
= ∅} = L(B).
Применённый в доказательстве теоремы способ получения ДКА по
НКА называется построением подмножеств».
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Алгоритм нахождения ДКА по НКА (построением подмножеств).
Вход.
НКА B = (Q, Σ, δ, Q
0
, F ).
Выход.
Эквивалентный ДКА A = (Q , Σ, δ , Q
0
, F ) без недостижимых состояний. для каждого P ⊆ Q label (P) := 0;
2. Q := {Q
0
};
3. пока (∃P ∈ Q : label (P) = 0) повторять
4.
для каждого a
∈ Σ
5.
δ (P, a) :=
q∈P
δ(q, a);
6.
Q
:= Q ∪ {δ (P, a)};
7.
label
(P) := 1;
8. F := {P ∈ Q | P ∩ F = Все состояния автомата A достижимы, поскольку каждое состояние в, кроме начального, получено переходом в него из ранее построенного состояния.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Пример построения ДКА по НКА
a b
Q
0
F
q
0
q
0
, q
1
q
0 1
0
q
1
q
2 0
0
q
2
q
2
q
1 0
1
a b
F
{q
0
}
{q
0
, q
1
}
{q
0
}
0
{q
0
, q
1
}
{q
0
, q
1
}
{q
0
, q
2
}
0
{q
0
, q
2
}
{q
0
, q
1
, q
2
}
{q
0
, q
1
}
1
{q
0
, q
1
, q
2
}
{q
0
, q
1
, q
2
}
{q
0
, q
1
, АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Определение недетерминированного конечного автомата с ε-переходами
Определяемые здесь автоматы будет удобно строить по заданным языкам.
Недетерминированным конечным автоматом с
ε-переходами
(ε-НКА) называется пятёрка B = (Q, Σ, δ, Q
0
, F ), где, Σ, Q
0
, F — те же, что ив случае НКА,
δ : Q × (Σ ∪ {ε}) → 2
Q
функция переходов.
ε-НКА может не сдвигаться по входной цепочке по окончании некоторых тактов (на таком такте автомат прочитывает Диаграмма переходов ε-НКА может содержать дуги,
помеченные ε.
ε-НКА распознает цепочку w ⇔ в диаграмме переходов существует путь изначального состояния в заключительное,
помеченный w Определение распознаваемой цепочки через обобщение функции переходов будет дано ниже.)
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Нормальные ε-НКА
Произвольный ε-НКА эквивалентен ε-НКА с единственным начальными единственным заключительным состоянием:
добавим следующим образом к исходному автомату состояния и f и объявим {q
0
} множеством начальных состояний, а {f} множеством заключительных состояний нового автомата.
ε-НКА вида (Q, Σ, δ, {q
0
}, {f}) будем называть нормальными.
В дальнейшем мы рассматриваем только нормальные ε-НКА.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Цепочки, распознаваемые (нормальным) ε-НКА
Пусть B = (Q, Σ, δ, {q
0
}, {f}) — (нормальный) ε-НКА.
Определим отношение ρ ⊆ Q
2
: (q, p) ∈ ρ ⇔ p ∈ δ(q, ε).
(q, p) ∈ ρ

(рефлексивно-транзитивное замыкание отношения ρ)
⇔ автомат может перейти из состояния q в состояние p, не сдвигаясь по входной цепочке.
Замыкание состояния q: Clo(q) = {p ∈ Q | (q, p) ∈ Замыкание множества состояний P ⊆ Q: Clo(P) =
q∈P
Clo
(q).
Обобщённая функция переходов ¯
δ : Q × Σ

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

Теорема
Класс языков, распознаваемых
ε-НКА, совпадает с классом языков,
распознаваемых НКА.
Д ока за тел ь ст в о.
Пусть B = (Q, Σ, δ, {q
0
}, {f}) — (нормальный) ε-НКА. Определим
НКА B = (Q, Σ, δ , Q
0
, {f}), где Q
0
= Clo(q
0
), δ (q, a) = ¯
δ(q, Пути, помеченные цепочкой w ∈ Σ

, в диаграммах переходов B и существуют или не существуют одновременно:
Таким образом, множества цепочек, распознаваемых B и B ,
совпадают.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Алгоритм нахождения ДКА по ε-НКА
Вход.
ε-НКА B = (Q, Σ, δ, {q
0
}, F ).
Выход.
Эквивалентный ДКА A = (Q , Σ, δ , Q
0
, F ) без недостижимых состояний. для каждого P ⊆ Q label (P) := 0;
2. Q
0
:= Clo(q
0
); Q := {Q
0
};
3. пока (∃P ∈ Q : label (P) = 0) повторять
4.
для каждого a
∈ Σ
5.
δ (P, a) :=
q∈P
¯
δ(q, a);
6.
Q
:= Q ∪ {δ (P, a)};
7.
label
(P) := 1;
8. F := {P ∈ Q | P ∩ F = Это видоизменение алгоритма, описанного на слайде 11. Замыкание) вычисляется поиском из состояния АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35

План
1
Недетерминированные конечные автоматы
2
Операции над автоматными языками
3
Регулярные языки
4
Автоматные (регулярные) фрагменты языков программирования
5
Пример нерегулярного языка
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Определение автоматного языка. Теорема о замкнутости класса автоматных языков относительно некоторых операций
Назовём язык автоматным, если он распознаётся некоторым конечным автоматом (каким. Обозначим через A класс всех автоматных языков.
Теорема
Класс A замкнут относительно объединения, пересечения,
дополнения, произведения и итерации.
Д ока за тел ь ст в о.
Замкнутость относительно объединения.
Пусть
B
1
= (Q
1
, Σ, δ
1
, {q
1
}, {f
1
}) и B
2
= (Q
2
, Σ, δ
2
, {q
2
}, {f
2
}) нормальные ε-НКА, Q
1
∩ Q
2
= ∅. Тогда язык L(B
1
) ∪ L(B
2
)
распознаётся следующим нормальным ε-НКА
(Q
1
∪ Q
2
∪ {q
0
, f}, Σ, δ
3
, {q
0
}, АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема продолжение доказательства
Замкнутость относительно произведения. Замкнутость относительно итерации. АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема окончание доказательства
Замкнутость относительно дополнения.
Пусть
A = (Q, Σ, δ, q
0
, F ) — (полный) ДКА. Тогда язык L(A)
распознаётся ДКА (Q, Σ, δ, q
0
, Q \ F Замкнутость относительно пересечения. K
∩ L = K АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35

Автоматность конечных языков
Предложение
Любой конечный язык является автоматным.
Д ока за тел ь ст в о.
Языки ∅, {ε}, {a} (где a — символ) распознаются следующими автоматами:
Любой язык, состоящий из одной цепочки, либо совпадает с либо является произведением конечного числа языков из одного символа, поэтому по предыдущей теореме такой язык является автоматным.
Любой конечный язык либо совпадает с ∅, либо является объединением конечного числа языков из одной цепочки, поэтому по предыдущей теореме такой язык является автоматным.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35

План
1
Недетерминированные конечные автоматы
2
Операции над автоматными языками
3
Регулярные языки
4
Автоматные (регулярные) фрагменты языков программирования
5
Пример нерегулярного языка
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Определение регулярного языка. Теорема Клини
Язык называется регулярным, если он может быть получен из конечных языков (или языков вида ∅, {ε}, {a}, где a — символ) в результате конечного числа операций объединения, произведения и итерации. Обозначим через R класс всех регулярных языков.
Теорема (теорема Клини)
R = Доказательство по предыдущим теореме и предложению. Покажем, что A ⊆ Пусть A = (Q, Σ, δ, q
0
, F ) — неполный ДКА. Индукцией по числу переходов автомата A докажем, что язык L(A) регулярен.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Теорема Клини: продолжение доказательства
База индукции.
Функция переходов δ нигде не определена.
Тогда L(A) = {ε}, если q
0
∈ F , и L(A) = ∅ иначе.
Существует ровно один переход δ(q, a) = Если q = q
0
, то имеем L(A) = {ε} при q
0
∈ F , а иначе L(A) = ∅.
Разберём всевозможные случаи, если q = q
0
:
r
= q
0
q
∈ F
r
∈ нет нет нет

нет нет да
{a}
нет да нет
{ε}
нет да да, да нет нет

да да да
{a}

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

L
(A
3
).
( Пусть w ∈ L(A). Если автомат A распознал w , не совершив перехода δ(q, a) = r, то w ∈ Если же переход δ(q, a) = r был совершён n
1 раз, то w
= w
0
aw
1
a
. . . w n−
1
aw для некоторых w
0
∈ L(A
1
),
w
1
, . . . , w n−
1
∈ L(A
2
), w n
∈ Так что w ∈ Пусть w принадлежит правой части ( ). Если w ∈ L(A
0
), то по определению автомата верно w ∈ Если w ∈ L(A
1
){a}(L(A
2
){a})

L
(A
3
), то w = w
0
aw
1
a
. . . w n−
1
aw для некоторых n
1, w
0
∈ L(A
1
), w
1
, . . . , w n−
1
∈ L(A
2
),
w n
∈ L(A
3
). Отсюда w ∈ АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Определение регулярных выражений
Регулярные языки можно задавать так называемыми регулярными выражениями
Регулярные выражения в алфавите (над алфавитом) Σ и языки,
которые они обозначают, определяются следующим образом:
символы
∅, ε и a (где a ∈ Σ) являются регулярными выражениями в Σ, обозначающими языки ∅, {ε} и {a} соответственно;
если r и s — регулярные выражения в Σ, обозначающие языки R и
S
соответственно, то (r |s), (rs) и являются регулярными выражениями в Σ, обозначающими языки R ∪ S, RS и R

соответственно.
Класс R совпадает с классом всех языков, определяемых регулярными выражениями.
Переносим соглашение о приоритетах операций над языками.
Пример: Σ = {a, b},
a

b
2
|bb

a
= {a m
b
2
| m
0} ∪ {b n
a
| n
1},
(a|b)

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

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

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

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

План
1
Недетерминированные конечные автоматы
2
Операции над автоматными языками
3
Регулярные языки
4
Автоматные (регулярные) фрагменты языков программирования
5
Пример нерегулярного языка
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35
Нерегулярность скобочного языка Предположим, что язык LB распознаётся некоторым ДКА Пусть n — число состояний этого автомата. Автомат A
распознаёт цепочку w = [[. . . [
n
] . . Изначального состояния автомат A при чтении n скобок последовательно переходит в состояния, обозначаемые q
1
, . . . , q Найдутся такие i < j, что q i
= q j
. Путь в автомате A,
помеченный цепочкой w , можно представить так:
Но тогда A распознаёт и цепочку [[. . . [
n−
(j−i)
] . . .]]
n
, не принадлежащую LB. Противоречие.
А. С. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков
18 февраля 2011 г.
34 / 35

Литература
Основная литература
Замятин А. П, Шур А. М. Языки, грамматики, распознаватели:
Учебное пособие. Екатеринбург : Изд-во Урал. унта, электронный вариант книги — на http://elar.usu.ru, поиск)
Дополнительная литература
Ахо А, Лам М, Сети Р, Ульман Дж. Компиляторы принципы,
технологии и инструментарий. М ООО ”И.Д. Вильямс”, 2008
Ахо А, Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М Мир, 1978
Мартыненко Б. К. Языки и трансляции Учеб. пособие. СПб.:
Издательство С.-Петербургского университета, 2004 (электронный вариант книги — на АС. Герасимов (СПбАУ РАН)
Лекции по теории формальных языков февраля 2011 г / 35


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал