Теория автоматов и формальных языков
ОСНОВНАЯ ЛИТЕРАТУРА
-
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1: Синтаксический анализ. М.: Мир, 1978. – 612 с.
-
Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. – 528 с.
-
Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учебное пособие. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 247 с.
-
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное.
-
Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988. – 128 c.
Занятие 1. Начальные понятия теории формальных языков
1. Перечислите слова языка , где и .
2. Для заданных языков L1 и L2 найти .
а) , ,
б) ,
3. Пусть A={a, b, с}. Равны ли языки и ?
4. Для заданного языка L в алфавите A={a, b} найти .
а) , б) .
5. Пусть A={a, b, с}, и . Сколько слов содержит язык ?
6. а) Пусть A={a, b} и L={aa, ab}. Найдите L2 и L3. Являются ли эти языки префиксными или суффиксными?
б) Пусть A={0, 1}. Является ли префиксным или суффиксным язык L={0, 11, 10, 01}?
7. Найдите конкатенации и языков L1={01, 001, 011} и L2={10, 100}.
8. Найдите L2, если .
9. Существуют ли такие языки L1 и L2, что языки
а) и , б) и
не равны между собой по мощности?
10. Пусть A={a, b} и f: – гомоморфизм.
а) Найдите , если f задан равенствами f(a)=abba и f(b)=..
б) Найдите , если f задан равенствами f(a)=ab и f(b)=abb.
11. Пусть f – гомоморфизм, определенный равенствами f(0)=a и f(1)=. Найдите и .
12. Пусть f – гомоморфизм, определенный равенствами f(0)=a, f(1)=bb и f(2)=. Опишите язык f({012}*).
13. Пусть A={a, b, c, d}. Существует ли такой гомоморфизм f: , что f(abc)=bac и f(da)=ba?
14. Существуют ли такой язык и такой гомоморфизм f: , что и ?
15. Существуют ли такой язык и такой гомоморфизм f: , что и ?
16. Описать язык, порождаемый грамматикой.
а) G=({S}, {a, b}, P, S), где ;
б) G=({S, D}, {a, b}, P, S), где ;
в) G=({S}, {a, b, c}, P, S), где;
г) G=({S, E, F}, {a, b, c}, P, S), где
;
д) G=({S, C, D, E, F}, {a, b}, P, S), где P={SCD,
.
17. Описать язык, порождаемый грамматикой.
а) G=({S, D, F}, {a, b}, P, S), где ;
б) G=({S, D, F}, {a, b}, P, S), где ;
в) G=({S}, {a, b}, P, S), где ;
г) G=({S, F, U}, {a}, P, S), где .
Занятие 2. Эквивалентность и виды грамматик
18. Каким классам принадлежат грамматики из упражнения 16?
19. Каким классам принадлежат грамматики из упражнения 17?
20. Эквивалентны ли грамматика G1 с правилами P1 и грамматика G2 с правилами P2, если
а) , ;
б) , ?
21. Какие из данных грамматик являются эквивалентными между собой?
а) , ; ;
б) , , .
22. Найти праволинейную грамматику, эквивалентную грамматике
а) ; б) .
23. Пусть . Постройте праволинейную грамматику для языка L, если каждое слово из L
а) начинается на букву c;
б) заканчивается на букву с.
24. Постройте контекстно-свободную грамматику, порождающую
а) язык ;
б) язык ;
в) язык ;
г) язык, состоящий из всех цепочек из нулей и единиц, имеющих четное число нулей и четное число единиц,
д) язык булевых функций с переменными a, b, c, логическими операциями &, и скобками (,).
Какие из этих грамматик являются линейными?
25. Постройте порождающую грамматику для языка вещественных констант с фиксированной точкой (например, 4., -12.7, 3.14159).
26. Постройте порождающую грамматику для языка вещественных констант с плавающей точкой (например, -4.625Е-18).
Занятие 3. Конечные автоматы-преобразователи
27. Являются ли детерминированными следующие словарные функции : {0, 1}{0, 1} ? Ответ обосновать.
а) , т.е. :
б) s-я буква y(s) в слове равна 0, если существует такое, что ; в противном случае .
в) s-я буква y(s) в слове равна 0, если при некотором выполняется неравенство ; в противном случае .
28. По заданным таблицам постройте диаграммы Мура.
-
а)
x(t)
z(t-1)
y(t)
z(t)
0
q0
0
q1
1
q0
0
q2
0
q1
1
q0
1
q1
1
q3
0
q2
1
q1
1
q2
1
q3
0
q3
0
q0
1
q3
0
q2
-
б)
A
Q
F
H
0
q0
0
q1
1
q0
0
q1
0
q1
1
q2
1
q1
0
q3
0
q2
1
q0
1
q2
1
q3
0
q3
0
q1
1
q3
1
q3
29. Постройте таблицы по заданным диаграммам Мура.
а) б)
30. По данным каноническим уравнениям автомата с входным алфавитом А={0, 1} и множеством состояний Q={0, 1} составьте таблицу и постройте диаграмму Мура.
31. Является ли словарная функция f: X*Y*, где X=Y={0; 1}, автоматной? Если да, то постройте автомат, реализующий ее.
а) f: б) f:
в) f: г) f:
д) f: е) f:
Занятие 4. Автоматы и автоматные языки.