НИУ Высшая школа экономики Кафедра управления разработкой программного обеспечения
Содержание курса
Алгоритмы и структуры данных
Do right things Do things right
Основная литература
Формальный язык
Алфавит и строки
Операции над строками
Итерация
Операция *
Пример бесконечного языка
Операции над языками
Обращение, конкатенация
Итерация
Еще пример
Замыкание * (звезда Клини)
Языки и автоматы
Автомат-распознаватель
Граф переходов автомата
Начальная конфигурация
Читает вход
Другой вход
Строгое определение ДКА
Множество состояний
Начальное состояние
Множество заключительных состояний
Функция переходов
Функция переходов
Обобщенная функция переходов
Язык, распознаваемый ДКА
Пример
Другой пример
Язык, распознаваемый ДКА
Еще примеры
Регулярные языки
Пример:
Недетерминированные конечные автоматы (НКА)
Как работает НКА ?
Недетерминированный конечный автомат (НКА): пример
НКА: еще пример
Определение НКА
Функция переходов
Обобщенная функция переходов
Обобщенная функция переходов
Язык, допускаемый НКА
Эквивалентность автоматов
Пример
Эквивалентность НКА и ДКА
НКА и регулярные языки
От НКА к ДКА (1)
От НКА к ДКА (2)
От НКА к ДКА (3)
От НКА к ДКА (4)
От НКА к ДКА (5)
От НКА к ДКА (6)
От НКА к ДКА (7)
От НКА к ДКА: суммируем
Алгоритм перевода НКА в ДКА
Пример
Алгоритм перевода НКА в ДКА
Пример
Алгоритм перевода НКА в ДКА
Пример
Алгоритм перевода НКА в ДКА
Пример
Теорема
Заметим:
Пример
В общем случае
Специальный случай
Свойства регулярных языков
Свойства
Говорят
Доказательство
Пример
Объединение
Пример
Конкатенация
Пример
Итерация
Пример
Дополнение
Пример

Алгоритмы и структуры данных

1. НИУ Высшая школа экономики Кафедра управления разработкой программного обеспечения

Алгоритмы и структуры
данных
2022-2023 учебный год
Нестеров Роман Александрович, PhD & Бессмертный Александр Игоревич
Департамент программной инженерии

2. Содержание курса

Do right things
Do things right

3. Алгоритмы и структуры данных

Основная литература
Хопкрофт Дж., Мотвани Р., Ульман Дж.
Введение в теорию автоматов, языков и
вычислений: Пер. с англ. - М.:
Издательский дом "Вильямс", 2008.
5

4. Do right things Do things right

Формальный язык
• Алфавит языка:
– Множество символов (букв)
• Язык – множество строк
• Строка (слово) :
– Последовательность символов
Примеры: “студент”, “123”, “house”, …
a , b , c , , z
6

5. Основная литература

Алфавит и строки
• Будем использовать алфавит из двух букв
a, b
• Строки (слова)
a
ab
abba
baba
u ab
v bbbaaa
w abba
aaabbbaabab
7

6. Формальный язык

Операции над строками
v b1b2 bm
w a1a2 an
v bbbaaa
w abba
• Конкатенация
wv a1a2 an b1b2 bm
wv abbabbbaaa
• Обращение
v
R
bm b2b1
v
R
aaabbb
8

7. Алфавит и строки

Итерация
w n ww
w
n
• Пример:
2
abba abbaabba
• Для любого слова w :
w
0
abba 0
9

8. Операции над строками

Операция *
• *- множество всех возможных слов в
алфавите
• Пример:
a , b
* , a , b , aa , ab , ba , bb , aaa , aab ,
*
a , b , aa , ab , ba , bb, aaa , aab ,
• Тогда язык в алфавите – любое
подмножество *
10

9. Итерация

Пример бесконечного языка
n n
L a b :n 0
ab
aabb
L
abb L
aaaaabbbbb
11

10. Операция *

Операции над языками
• Обычные теоретико-множественные операции:
a , ab, aaaa bb, ab {a , ab, bb, aaaa }
a , ab, aaaa bb, ab {ab }
a , ab, aaaa bb, ab a , aaaa
• Дополнение:
L * L
a , ba , b, aa , ab, bb, aaa ,
12

11. Пример бесконечного языка

Обращение, конкатенация
LR w R : w L
ab, aab, baba R ba , baa , abab
L1L2 xy : x L1 , y L2
a , ab, ba b, aa
ab , aaa , abb , abaa , bab , baaa
13

12. Операции над языками

Итерация
n
L LL
L
n
• Пример:
3
a , b a , b a , b a , b
aaa , aab , aba , abb, baa , bab, bba , bbb
• Специальный случай:
0
L
0
a , bba , aaa
14

13. Обращение, конкатенация

Еще пример
2
n n m m
L a b a b : n , m 0
L a n bn : n 0
2
aabbaaabbb L
15

14. Итерация

Замыкание * (звезда Клини)
0
1
2
L* L L L
• Пример:
,
a , bb ,
a , bb *
aa , abb , bba , bbbb,
aaa , aabb , abba , abbbb ,
16

15. Еще пример

Языки и автоматы

16. Замыкание * (звезда Клини)

Вычисление
Оперативная память
Вход
Процессор
Выход
Программа
18

17. Языки и автоматы

Абстрактная машина
Оперативная память
Автомат
Внутр.
состояние Процессор
Входн. память
Выходн. память
Программа (в памяти)
19

18.

Виды автоматов
В зависимости от оперативной памяти
• конечные автоматы
Нет оперативной памяти
• магазинные (стековые) автоматы
Стек
• машины Тьюринга
‘Неограниченная’ память
20

19.

Конечный автомат
Оперативная память
Конечный
автомат
Входн. память
Выходн. память
Слабые вычислительные возможности
21

20.

Конечный автомат - распознаватель
Оперативная память
Конечный
автомат
Входн. память
Да или Нет
Распознает, принадлежит ли слово языку
22

21.

Автомат-распознаватель
Вход
Строка
Конечный
автомат
Выход
“Да”
или
“Нет”
23

22.

Граф переходов автомата
аbba - распознаватель
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
начальное
состояние
переход
состояние
a, b
q4
финальное
состояние
“Да”
24

23. Автомат-распознаватель

Начальная конфигурация
a b b a
Входная строка
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
25

24. Граф переходов автомата

Читает вход
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
26

25. Начальная конфигурация

a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
27

26. Читает вход

a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
28

27.

a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
Выход: “Да”
слово допускается автоматом
29

28.

Другой вход
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
30

29.

a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
31

30. Другой вход

a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
32

31.

a b a
a, b
b
q0 a
Выход:
q5 “Нет”
a, b
a
a
b
q1 b q2 b q3 a
q4
Слово отвергается автоматом
33

32.

Строгое определение ДКА
• Детерминированный конечный автомат (ДКА)
M Q , , , q0 , F
Q
: множество состояний
: входной алфавит
: функция переходов
q0 : начальное состояние
F
: множество заключительных состояний
34

33.

Множество состояний Q
Q q0 , q1 , q2 , q3, q4 , q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
35

34. Строгое определение ДКА

q
Начальное состояние 0
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
36

35. Множество состояний

Множество заключительных
состояний F
F q4
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
37

36. Начальное состояние

Функция переходов
:Q Q
q0 , a q1
a, b
q0 , b q5
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
38

37. Множество заключительных состояний

q0
q1
q2
q3
q4
q5
a
q1
q5
qq25
q4
q5
q5
Функция переходов
b
q5
q2
q3
q5
q5
q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
39

38. Функция переходов

Обобщенная функция переходов *
* : Q * Q
* q0 , ab q2
* q0 , abba q4
a, b
* q0 , abbaa q5
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
40

39. Функция переходов

Язык, распознаваемый ДКА
Пусть M – ДКА
Определение:
Язык L M распознается автоматом M , если он
состоит из всех строк, допускаемых этим автоматом.
Другими словами:
L M = { строки, которые переводят M в
заключительное состояние}
41

40. Обобщенная функция переходов

Пример
M
L M abba
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
42

41. Язык, распознаваемый ДКА

Другой пример
M
L M , ab????
, abba
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
43

42. Пример

Язык, распознаваемый ДКА
M Q , , , q0 , F
Для ДКА
Язык, распознаваемый M :
заключ.
состояния
L M w * : * q0 , w F
алфавит
функция
переходов
начальное
состояние
44

43. Другой пример

Еще примеры
L M a n b????
:n 0
a, b
a
q0
b
q1
a, b
допустить
q2
“ловушка”
45

44. Язык, распознаваемый ДКА

L M = ???
a, b
q0
a
q1
b
a
q3
b
q2
допустить
a, b
46

45. Еще примеры

L M = ???
0
1
0,1
1
0
0
00
1
001
0
47

46.

Регулярные языки
Определение:
Язык L – регулярный, если существует ДКА M
такой, что L L M .
Все регулярные языки составляют класс регулярных
языков
48

47.

Пример:
Язык L awa : w a , b * регулярный:
a
b
b
q0
a
q2
q3
a
b
q4
a, b
49

48. Регулярные языки

Недетерминированные
конечные автоматы (НКА)
Обобщение ДКА. Позволяет:
– выбирать следующее состояние из нескольких
возможных
• угадывание
– Помеченные пустым символом переходы.
• изменять состояние без чтения очередного
входного символа
Зачем? Большая гибкость.
– Проще строить, проще доказывать свойства.
50

49. Пример:

Как работает НКА ?
• Слово w допускается НКА, если существует
последовательность переходов (подсказок),
переводящая автомат в одно из заключительных
состояний (при этом слово полностью прочитано).
• Язык, распознаваемый НКА – множество всех
допускаемых слов.
51

50. Недетерминированные конечные автоматы (НКА)

Недетерминированный конечный
автомат (НКА): пример
0
q0
1
q1
0, 1
q2
L , 10, 1010, 101010, ...
10 *
52

51. Как работает НКА ?

НКА: еще пример
q0
a
q1
b
q2
q3
L ab, abab, abab, ...
ab
53

52. Недетерминированный конечный автомат (НКА): пример

Определение НКА
M Q, , , q0 , F
Q : Мн-во состояний q0 , q1, q2
: Входной алфавит a, b
: Функция переходов
q0 : Начальное состояние
F : Заключительные состояния
54

53. НКА: еще пример

Функция переходов
0
q0
1
q1
0, 1
q2
q0 , 1 q1
q0 , 0
q0 , q0 , q2
q1, 0 q0 , q2
q2 ,1
55

54. Определение НКА

Обобщенная функция переходов *
q5
q4
a
q0
a
a
b
q1
q2
q3
* q0 , a q1
* q0 , aa q4 , q5
* q0 , ab q2 , q3 , q0
56

55. Функция переходов

Обобщенная функция переходов
q j * qi , w
в том и только том случае, когда
имеется путь от qi к q j
с пометкой w
57

56. Обобщенная функция переходов

Язык, допускаемый НКА M
F q0 , q5
q0
q5
q4
a
a
a
b
q1
q2
q3
* q0 , aa q4 , q5
* q0 , ab q2 , q3 , q0
aa L( M )
ab L M
58

57. Обобщенная функция переходов

Эквивалентность автоматов
Для ДКА и НКА :
Автоматы M1 и M 2 эквивалентны
если
L M1 L M 2
(т.е. их языки совпадают)
59

58. Язык, допускаемый НКА

Пример
L M1 {10} *
0
q0
1
НКА
q1
0, 1
ДКА
L M 2 {10} *
q2
0,1
0
q0
1
q1
1
q2
0
60

59. Эквивалентность автоматов

Эквивалентность НКА и ДКА
Любой ДКА является также НКА
Язык, распознаваемый ДКА будет
распознаваться также и НКА
Слабее ли ДКА, чем НКА?
Ответ: НЕТ!
Язык, распознаваемый НКА
распознается также и ДКА
Теорема. Для любого НКА можно
построить эквивалентный ему ДКА.
61

60. Пример

НКА и регулярные языки
Для любого НКА имеется
эквивалентный ДКА
Языки, распознаваемые ДКА –
регулярные
Класс языков, распознаваемых НКА,
совпадает с классом регулярных
языков.
62

61. Эквивалентность НКА и ДКА

От НКА к ДКА (1)
НКА
a
q0
a
q1
q2
b
ДКА
q0
63

62. НКА и регулярные языки

От НКА к ДКА (2)
a
НКА
q0
a
q1
q2
b
ДКА
q0
a
q1, q2
64

63. От НКА к ДКА (1)

От НКА к ДКА (3)
a
НКА
q0
a
q1
q2
b
ДКА
q0
a
q1, q2
b
65

64. От НКА к ДКА (2)

От НКА к ДКА (4)
a
НКА
q0
a
q1
q2
b
ДКА
a
q0
a
q1, q2
b
66

65. От НКА к ДКА (3)

От НКА к ДКА (5)
НКА
a
q0
a
q1
q2
b
ДКА
a
b
q0
a
q1, q2
b
67

66. От НКА к ДКА (4)

От НКА к ДКА (6)
a
НКА
q0
a
q1
q2
b
ДКА
a
b
q0
a
q1, q2
a, b
b
68

67. От НКА к ДКА (5)

От НКА к ДКА (7)
НКА
a
q0
a
q1
q2
b
ДКА
a
b
q0
a
q1, q2
a, b
b
69

68. От НКА к ДКА (6)

От НКА к ДКА: суммируем
• Пусть дан НКА M
• Мы хотим построить эквивалентный ему ДКА M
такой, что L M L(M )
70

69. От НКА к ДКА (7)

• Пусть НКА имеет состояния
q0 , q1, q2 ,...
• Тогда состояния ДКА – множества состояний НКА
, q0 , q1 , q1, q2 , q3 , q4 , q7 ,....
71

70. От НКА к ДКА: суммируем

Алгоритм перевода НКА в ДКА
1. Начальное состояние НКА: q0
Начальное состояние ДКА: q0
72

71.

Пример
a
НКА
q0
a
q1
q2
b
ДКА
q0
73

72. Алгоритм перевода НКА в ДКА

2. Для каждого состояния ДКА qi , q j ,..., qm
вычислить в НКА
* qi , a ,
* q j , a , ...
- объединение
Пусть qi , q j ,..., qm
результатов этих вычислений.
Тогда добавляем переход
qi , q j ,..., qm , a qi , q j ,..., qm
74

73. Пример

a
НКА
q0
a
q1
q2
b
* (q0 , a) {q1, q2}
ДКА
q0
a
q1, q2
q0 , a q1, q2
75

74. Алгоритм перевода НКА в ДКА

Повторять шаг 2 для всех входных символов, пока не
будут построены все возможные переходы.
76

75. Пример

НКА
a
q0
a
q1
q2
b
ДКА
a
b
q0
a
q1, q2
a, b
b
77

76. Алгоритм перевода НКА в ДКА

3. Для каждого состояния ДКА
qi , q j ,..., qm
если состояние q j - заключительное в НКА
qi , q j ,..., qm
то
объявляется заключительным в ДКА
78

77. Пример

НКА
a
q0
a
q1
q2
b
a
b
ДКА
q0
a
q1 F
q1, q2
q1, q2 F
b
a, b
79

78. Алгоритм перевода НКА в ДКА

Теорема
Пусть M - произвольный НКА,
и пусть M - ДКА, получающийся из M
в результате описанной выше процедуры.
Тогда автоматы M и M эквивалентны, т.е.
L M L M
80

79. Пример

Заметим:
Для любого конечного автомата (ДКА и НКА) можно
построить эквивалентный НКА с одним
заключительным состоянием.
81

80. Теорема

Пример
a
НКА
b
a
b
Эквивалентный НКА
a
a
b
b
82

81. Заметим:

НКА
В общем случае
Эквивалентный НКА
Одно
Заключительное
состояние
83

82. Пример

Специальный случай
НКА без заключительного состояния
Добавим заключительное
состояние
84

83. В общем случае

Свойства регулярных
языков

84. Специальный случай

Свойства
Пусть L1 и
Докажем:
L2 - регулярные языки
Объединение: L1 L2
Конкатенация: L1L2
Итерация: L1 *
Дополнение: L1
Регулярные
языки
Пересечение: L1 L2
86

85. Свойства регулярных языков

Говорят
Регулярные языки замкнуты относительно:
– объединения: L1 L2
– конкатенации: L1L2
– итерации: L1 *
L1
– дополнения:
– пересечения: L1 L2
87

86. Свойства

Доказательство
Пусть языки L1 и L2
допускаются НКА M1 и M 2 т.е.
L M1 L1
M1
L M 2 L2
M2
одно закл. состояние
88

87. Говорят

Пример
M1
L1 a b
n
a
b
M2
L2 ba
b
a
89

88. Доказательство

Объединение L1 L2
НКА
M1
M2
90

89. Пример

НКА для L1 L2 a nb b, a
L1 a nb
a
b
L2 ba
b
a
91

90. Объединение

Конкатенация L1L2
НКА
M1
M2
92

91. Пример

n
n
L
L
a
b
ba
a
bba
НКА для 1 2
L1 a nb
L2 ba
a
b
b
a
93

92. Конкатенация

Итерация L1 *
НКА
M1
94

93. Пример

НКА для
n *
L1* a b
a
b
L1 a nb
95

94. Итерация

Дополнение
Для дополнения L языка L :
• Возьмем ДКА M который допускает L и построим M
такой что:
– Каждое финальное состояние M является
нефинальным для M
– И наоборот нефинальное – финальным
• Получаем:
L M L M L
96

95. Пример

a, b
a
b
a, b
a, b
a
L a b
n
L a b
n
b
a, b
97

96. Дополнение

Пересечение
Для регулярных языков L1 и L2 :
L1 L2 L1 L2
L1 L2
регулярн
регулярн
L1
L1
L2
L2
регулярн
регулярн
L1 L2 L1 L2
L1 L2
регулярн
98

97. Пример

• Регулярные языки:
L2 bmba
L1 a k bl
k , l, m 0
Язык L1 L2 b b
m
регулярный
99
English     Русский Правила