Теория конечных языков и автоматов. Курс лекций П. Н. Иваньшин 2

• Название: Курс лекций П. Н. Иваньшин 2
• Анкор: Теория конечных языков и автоматов
• Дата: 29.11.2021
• Размер: 0.61 Mb.
• Имя файла: Теория конечных языков и автоматов.pdf
• Тип: Курс лекций; #285247
• страница: 2 из 5

Тогда существует такая константа n, что для z ? L, |z| > n найдутся такие u, v, w ? ?
?
, v 6= ?, что z = uvw и uv k
w ? L
для всех k ? 0.
При этом длина строки uw не больше n. Далее, если M  автомат,
принимающий язык L и M имеет q состояний, то n < q. Кроме того,
можно утверждать, что z = uvw, где длина uv не больше q.
Доказательство. Пусть L принимаем автоматом M = (?, Q, s
0
, ?, F )
Пусть ?(s i
, a i
) = s i+1
для i = 1, . . . , t; обозначим это через
(s
1
, a
1
a
2
a
3
· · · a t
) ` (s t+1
, ?).
L
содержит слово длины m, где m > q, пусть w = a
1
a
2
a
3
· · · a m
. За- метим, что если (s
1
, a
1
a
2
a
3
· · · a m
) ` (s m
, ?)
, то s m
 принимающее со- стояние. Так как m > q, в процессе чтения w, M дважды проходит одно и то же состояние. Следовательно, (s
1
, a
1
a
2
a
3
· · · a j?1
) ` (s k
, ?)
и
(s
1
, a
1
a
2
a
3
· · · a k?1
) ` (s k
, ?)
для некоторого j < k и одновременно
(s j
, a j
a j+1
· · · a m
) ` (s m
, ?)
и(s j
, a k
a k+1
· · · a m
) ` (s m
, ?).
Следовательно
(s
1
, a
1
a
2
a
3
· · · a m
) ` (s m
, ?)
и(s
1
, a
1
a
2
· · · a j?1
a k
a k+1
· · · a m
) ` (s m
, ?).
В то же время, (s j
, a j
a j+1
· · · a k?1
) ` s j
, то есть существует a j
a j+1
· · · a k?1
- петля в M и, следовательно,
(s
1
, a
1
a
2
· · · a j?1
(a j
a j+1
· · · a k?1
)
n a
k a
k+1
· · · a m
) ` (s m
, ?).

20
Глава 2. Автоматы
Положим u = a
1
a
2
· · · a j?1
, v = a j
a j+1
· · · a k?1
, и w = a k
a k+1
· · · a m
. Тогда uv n
w ? L
для всех n ? N.
Так как |uw| < |uvw| = m, если |uw| > q, мы можем повторять этот процесс для uv пока u(v)
n w ? L
для всех n ? N, где |uw| < q. Пусть v 
первый цикл в слове z. Тогда длина uv не больше q.
Теорема 9. Язык L = {a n
b n
|N ? 1}
нерегулярен.
Доказательство. Пусть L = {a n
b n
|N ? 1}

регулярен. Так как L бес- конечен, существуют такие строки u, v, w ? ?
?
, v 6= ?, что u(v)
?
w ? L
Рассмотрим все возможные частные случаи.
1) Пусть u = a m?k
, v = a k
, w = b m
. Тогда a m?k a
2k b
m
= a m+k b
m
? L
,
что противоречит определению L.
2) Пусть u = a m
, v = b k
, w = b m?k
. Аналогично 1) получим противо- речие определению L.
3) Пусть u = a m?k
, v = a k
b r
, w = b m?r
. Тогда a m?k a
k b
r a
k b
r b
m?r
? L
,
опять противоречие определению L.
Следовательно, L нерегулярен.
Задачи
1. Выяснить, которые из приведенных множеств регулярны.
a) {a n
b
2n a
n
|n ? 1}
;
b) {(ab)
n
|n ? 1}
;
c) {a n
b n
a n
|n ? 1}
;
d) {a n
b m
|m, n ? 1}
;

e) {ww|w ? ?
?
и |?| = 2};
f) {a
2n
|n ? 1}
;
g) {w ? {a, b}
?
|w содержит одно и то же количество a и b };
h) {w ? {a, b}
?
|w содержит ровно четыре b };
i) {ww
R
|w ? {a, b}
?
длина w не больше трех };
j) {ww
R
|w ? {a, b}
?
}
2.5 Алгоритмы сравнения языков и автома- тов
Теорема 10. Существует алгоритм, выявляющий пустоту языка M(L),
принимаемого данным автоматом M.

2.5. Алгоритмы сравнения языков и автоматов
21
Доказательство. Пусть M имеет n состояний. Тогда M(L) пуст ? s
0
не конечное состояние и не существует строки длины не больше n, при- нимаемой M, поскольку кратчайшая из возможных строк не проходит дважды через одно и то же состояние. Так как таких строк конечное число, их все можно перебрать.
Теорема 11. Существует алгоритм, отвечающий на вопрос о совпа- дении языков для двух различных автоматов.
Доказательство. Пусть автоматы M
1
и M
2
принимают языки M
1
(L)
и
M
2
(L)
, соответственно. Тогда определены автоматы, принимающие язы- ки M
1
(L)
T M
2
(L)
, и M
1
(L)
S M
2
(L)
. Следовательно, можно построить автомат для языка (M
1
(L)
T M
2
(L))
S(M
2
(L)
T M
1
(L))
,  симметриче- скую разность языков M
1
(L)
и M
2
(L)
. Это множество пусто ? M
1
(L) =
M
2
(L)
. Следовательно, можно использовать предыдущую теорему для ответа на поставленный вопрос.
Теорема 12. Существует алгоритм сравнения двух регулярных язы- ков.
Доказательство. Пусть даны языки L
1
и L
2
. Построим такие автоматы
M
1
и M
2
, что L
1
= M
1
(L)
и L
2
= M
2
(L)
. Далее применим предыдущую теорему.
Лемма 2. Пусть M содержит n состояний. Язык L, соответству- ющий M бесконечен ? существует такое слово в L, что его длина больше n но меньше 2n.

Доказательство. ? Пусть L бесконечен. По лемме о накачке, существу- ет набор u, v, w ? ?
?
, uv m
w ? L
для всех m ? N, кроме того |uw| ? n.
Также можно считать, что |v| < n. Так как v 6= ?, существует m
0
? N,
n < |uv m
0
w| = |uw| + m|v| < 2n
Теорема 13. Существует алгоритм, определяющий конечность языка
M (L)
Доказательство. Пусть M имеет n состояний. Тогда M(L) бесконечен
? M
принимает строку s n ? |s| ? 2n. Так как таких слов конечное число, простым перебором можно ответить на заданный в формулировке утверждения вопрос.
Теорема 14. Существует алгоритм, определяющий конечность языка
M (L)

22
Глава 2. Автоматы
Доказательство. Как и в предыдущей теореме рассмотрим все слова s длины n ? |s| ? 2n. Если ни одно такое слово не допустимо, автомат конечен.
Теорема 15. Существует алгоритм, позволяющий определить, верно ли что L
1
? L
2
Доказательство. Сначала построим автомат для L
1
T ?
?
\ L
2
. Язык
L
1
T ?
?
\ L
2
пуст ? L
1
? L
2
Задачи
1. Доказать, что существует алгоритм проверки тождества M(L) =
?
?
2. Доказать, что существует алгоритм проверки того, содержит ли
M (L)
слова, включающие данную букву алфавита ?.
3. Доказать, что существует алгоритм проверки того, содержит ли
M (L)
слова, включающие все буквы алфавита ?.
4. Доказать, что существует алгоритм проверки того, содержит ли
M (L)
слова, начинающиеся с данной буквы алфавита ?.
5. Доказать, что существует алгоритм проверки того, содержит ли
M (L)
слова четной длины.
6. Доказать, что существует алгоритм проверки того, содержит ли
M (L)
слова длины mk, для фиксированного m ? N.
2.6 Автоматы Мили и Мура
Определение 16. Автомат Мура  набор (?, A, S, s
0
, ?, ?)
S
 конечное множество состояний, содержащее начальное состо- яние s
0
?
 алфавит ввода.
A
 алфавит вывода.
? : S Ч ? ? S
 функция перехода.
? : S ? A
 функция вывода.

При обработке слова w ? ?
?
сначала действует ?, потом ?.
Пример:
? = {a, b}
, A = {0, 1}, S = {s
0
, s
1
, s
2
}
, ?(s
0
) = 1
, ?(s
1
) = ?(s
2
) = 0
. ?
задана по автомату
//
s
0
/1
b
,,
a

s
1
/0
a ll b
,,
s
2
/0
a tt b
gg

2.6. Автоматы Мили и Мура
23
Введя слово aba на выходе получим 1101.
Определение 17. Автомат Мили  набор (?, A, S, s
0
, ?, ?)
S
 конечное множество состояний, содержащее начальное состо- яние s
0
?
 алфавит ввода.
A
 алфавит вывода.
? : S Ч ? ? S
 функция перехода.
? : S Ч ? ? A
 функция вывода.
Пример:
Пусть S = {s
0
, s
1
, s
2
}
, A = {0, 1}, ? = {a, b}, ? и ? определены по автомату
//
s
0
a/1
''
b/0

s
1
b/0
kk a/1
kk s
2
a/0
QQ
b/0 77
Ввод aaabb дает вывод 11000.
Определение 18. Строка вывода автомата Мили эквивалентна стро- ке вывода автомата Мура если она равна подстроке автомата Мура без первого символа. То есть, при выводе автоматом Мура 010010101, его эквивалент в автомате Мили  10010101.
Построим автомат Мили с выводом, эквивалентным данному автома- ту Мура. Для этого преобразуем
//
s
0
/a
0
b
,,
s
1
/a
1
в
//
s
0
b/a
1
))
s
1
Аналогично s i
/a i
b
22
s j
/a j
в s i
b/a j
55
s j
Заметим, что количество состояний при этом не меняется.
Построение автомата Мура, эквивалентного данному автомату Мили подразумевает, вообще говоря, введение новых состояний.
Например,
a/x
''
s c/z
%%
b/y
66
перейдет в a
,,
s x
/x c/z
''
b
22
s y
/y c/z
GG

24
Глава 2. Автоматы
Задачи
1. Для автомата Мура найти эквивалентный автомат Мили.
a)
b)
c)
2. Для автомата Мили построить эквивалентный автомат Мура.
a)
b)

2.6. Автоматы Мили и Мура
25
c)

26
Глава 2. Автоматы

Глава 3
Грамматики
3.1 Формальные грамматики
Определение 19. Формальная грамматика ?  набор (N, ?, S, P ).
* ?  набор (алфавит) терминальных символов
* N  набор (алфавит) нетерминальных символов
* P  набор правил вида: ѕлевая частьї ? ѕправая частьї, где:
?
ѕлевая частьї  непустая последовательность терминалов и нетер- миналов, содержащая хотя бы один нетерминал
?
ѕправая частьї  любая последовательность терминалов и нетер- миналов
* S  стартовый (начальный) символ из набора нетерминалов.
Определение 20. Пусть W и W
0
 элементы (N S ?)
?
и v ? v
0

правило P , тогда W = uvw, W
0
= uv
0
w
, обозначается через W ? W .
Пусть
W
1
? W
2
? W
3
? · · · ? W
n
,
для n ? N, тогда говорят, что W
n выводится из W
1
. Обозначим это через W
1
?
n
W
n и назовем выводом. Набор всех строк из элементов
?
, порожденных правилами P , называется языком, порожденным грамматикой ?, и обозначается ?(L).
Определение 21. Каждому правилу P ? w
1
w
2
. . . w n
соответствует дерево
P
w
1
w
2
w n
27

28
Глава 3. Грамматики
Пример 1. S ? A + B
S
A
+
B.
Определение 22. Если деревья, соответствующие правилам вывода некоторой строки, связны, то они образуют дерево с корнем S, на- зываемое деревом разбора (parse tree, derivation tree). Если в выводе встречается правило A ? B то в дереве разбора есть ребро, соединя- ющее A с B. Символы A и B называются вершинами, при этом B 
потомок A. Терминалы не имеют потомков, следовательно, являются листьями дерева.
Определение 23. Контекстно-свободная грамматика  грамма- тика, в которой все правила P имеют вид A ? W , где A ? N.
Контекстно-зависимая грамматика  грамматика, в которой встречаются правила вида aAb ? W , где A ? N, ab 6= ?.
Определение 24. Регулярная грамматика  такая контекстно- свободная грамматика ? = (N, ?, S, P ), что ?p ? P p = n ? w, где w
 либо пустое слово ?, либо строка w содержит не более одного нетерминала, являющегося при этом последним символом w.

Определение 25. Линейная регулярная грамматика  такая кон- текстно-свободная грамматика ? = (N, ?, S, P ), что ?p ? P p = n ?
w
, где w есть либо xY , либо x, либо ?, где x ? ?, Y ? N.
Теорема 16. Язык порожден линейной регулярной грамматикой тогда и только тогда, когда он порожден регулярной грамматикой.
Доказательство. (?)  Очевидно.
(?): 1. Рассмотрим новые правила вывода для p = A ? a
1
a
2
· · · a n
B
,
p
1
= A ? a
1
A
1
, . . . , p n
= A ? a n
A
n
. Получим новый язык L
0 2. Ясно, что L
0
? L
. L ? L
0
по построению.
Теорема 17. Язык регулярен тогда и только тогда, когда он порожден регулярной грамматикой.
Доказательство. Построим автомат, соответствующий языку, порож- денному регулярной грамматикой и наоборот, по автомату построим ре- гулярную грамматику.
Вторая задача решается конструктивно. Пусть допустимое слово 
aabc
, тогда рассмотрим ? = s
0
, s
1
, s
2
, s
3
, s
4
, N = a, b, c, S = s
0
и правила s
0
? as
1
, s
1
? as
2
, s
2
? bs
3
, s
3
? cs
4
, s
4
? ?
. Тогда правило s
4
? ?
применяется только для терминала s
4

3.1. Формальные грамматики
29

Определение 26. ?
M
= (N, T, S, P )
 грамматика, ассоциирован- ная с автоматом M = (?, Q, s
0
, T, F )
. Для нее N = Q, s
0
= S
. Правило s
i
? as j
принадлежит P тогда и только тогда, когда F (a, s i
) = s j
, а s
j
? ?
 тогда и только тогда, когда s j
 конечное состояние.
Лемма 3. Язык L
1
, принимаемый M, совпадает с языком L
2

, порож- денным ?
M
Обратная процедура. Пусть дана регулярная грамматика ? = (N, T, S, P )
в линейной форме. Определим недетерминированный автомат M
?
, при- нимающий эту линейную грамматику. Итак, M
?
= (?, Q, s
0
, ?, F )
, где
? = T N
 множество нетерминалов вместе с дополнительным нетер- миналом t, s
0
= S

. Множество ? определено следующим образом: B ?
?(a, A)
если A ? aB ? P ; t ? ?(a, A), если A ? a ? P . Состояние B ? T
если B ? ? ? P или B = t.
Лемма 4. Язык L
1
, принимаемый M
?
, совпадает с языком L
2
, порож- денным ?.
Задачи
1. Найти язык, порожденный грамматикой ? = (N, T, S, P ), где a) N = {S, A, B}, T = {a, b}, а множество правил P состоит из
S ? AB, A ? aA, A ? ?, B ? Bb, B ? ?.
b) N = {S, A, B}, T = {a, b}, множество правил P состоит из
S ? aB, B ? bA, A ? aB, B ? b.
c) N = {S, A, B}, T = {a, b}, множество правил P состоит из
S ? aA, B ? aA, S ? bB, A ? aB,
B ? bB, A ? bA, B ? b, A ? a.
d)N = {S, A, B, C}, T = {a, b}, множество правил P состоит из
S ? C, A ? aB, C ? bC, B ? bB,
C ? aA, B ? aA, A ? bA, B ? ?.
2. Найти грамматику, порождающую язык

30
Глава 3. Грамматики a) ww r
, где w  строка из a и b, а w r
 строка, записанная в обратном порядке. Например, abba, abaaba, abbbba ? ww r
b) wcw r
, где w ? a, b
?
, а w r
 строка, записанная в обратном порядке.
c) L = {w|w ? {a, b}
?
, w = w r
}
d) aa
?
bb
?
e) (abc)
?
f) (ab)
?
? (ac)
?
g) ac(bc)
?
d h) (a
?
ba
?
ba
?
b)
?
i) (a
?
b) ? (b
?
a)
?
j) (a
?
b) ? (c
?
b) ? (ac)
?
3. Построить автомат, принимающий язык, порожденный граммати- кой ? = (N, T, S, P ).
a) N = {S, A, B}, T = {a, b}, P состоит из
S ? aB, B ? bA, A ? aB, B ? b.
b) N = {S, A, B}, T = {a, b}, P состоит из
S ? aA, B ? aA, S ? bB, A ? aB,
B ? bB, A ? bA, B ? b, A ? a.
c) N = {S, A, B, C}, T = {a, b}, P состоит из
S ? C, A ? aB, C ? bC, B ? bB,
C ? aA, B ? aA, A ? bA, B ? ?.
d) N = {S, A, B, C}, T = {a, b}, P состоит из
S ? C, C ? b, C ? aA, A ? aA,
C ? aC, A ? a, C ? a, A ? ?.
e) N = {S, A, B, C}, T = {a, b}, P состоит из
S ? C, C ? aaC, C ? abC,
C ? baC, C ? bbC, C ? ?.
f) N = {S, A, B, C}, T = {a, b}, P состоит из
S ? C, B ? aB, C ? bC, B ? bB, C ? aA,
B ? a, A ? bC, B ? b, A ? aB.

3.1. Формальные грамматики
31 4. Найти грамматику, порождающую язык, принимаемый автоматом a)
b)
c)
d)
e)

32
Глава 3. Грамматики
3.2 Нормальные формы Хомского и Грейба- ха
Определение 27. Контекстно-свободная грамматика представлена в нормальной форме Хомского (Chomsky normal form), если ?p ? P
либо p = A ? BC либо p = A ? a, где A, B, C ? N, a ? T .
Определение 28. Контекстно-свободная грамматика представлена в нормальной форме Грейбаха (Greibach normal form) если ?p ? P p =
A ? aW
, где a ? T , а W  строка (может пустая) из нетерминалов.

Лемма 5. Пусть ? = (N, T, S, P )  грамматика, и UV ?
?
W

(U, V, W ?
(N
S T )
?
)  вывод длины n. Тогда строка W может быть представ- лена в виде W
1
W
2

, где U ?
?
W
1
, V ?
?
W
2
 выводы в ?, не длиннее n шагов.
Доказательство. Доказательство по индукции. Индукция по количе- ству применений правил P .
Определение 29. Левый вывод слова w в языке, порожденном ? 
вывод, порожденный заменой крайнего левого нетерминала правилом из
P
на каждом шаге вывода
Лемма 6. Пусть w ? L(?), где L(?)  язык, порожденный граммати- кой ? = (N, T, S, P ). Тогда существует левый вывод w.
Доказательство. Индукция по числу применений правил выводы из P .
n = 1
, правило имеет вид S ? w, и, очевидно, является левым. Пусть n = k > 1
, и S ? w, пусть S ? UV , где U, V ? (N S T )
?
. По лемме

5 существуют выводы U ?
?
w
1
, V ?
?
w
2
, где w = w
1
w
2

. Так как оба этих вывода длины не больше k, существуют левые выводы U ?
?
w
1
,
V ?
?
w
2

. Следовательно, S ? UV ?
?
w
1
V ?
?
w
1
w
2
 левый вывод w

Лемма 7. Пусть ? такая грамматика, что L(?) не содержит пустого слова. Построим грамматику ?
0
начиная с правил из ? и
(i) удалив ?-правила;
(ii) для каждого правила p = A ? w ? P , где w = w
1
X
1
w
2
X
2
. . . w n
X
n и нильпотентов X
1
, X
2
, . . . , X
n в w, положим P = 2
{1,...,n}
. Теперь для p ? P
определим правило A ? w p
, где w p
 строка w без элементов X
i
,
i ? p
. X
i порождают ?-правила.

Тогда L(?
0
) = L(?)

3.2. Нормальные формы Хомского и Грейбаха
33
Доказательство. Пусть L  язык порожденный ? = (N, T, S, P ), и L
0

?
0
= (N, T, S, P
0
)
. Язык L
0
? L

по построению ?
0
Докажем, что L ? L
0

, пусть w ? L. По индукции по количеству шагов в выводе покажем, что если S ?
?
w