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

ОСНОВНАЯ ЛИТЕРАТУРА

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1: Синтаксический анализ. М.: Мир, 1978. – 612 с.

2. Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. – 528 с.

3. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учебное пособие. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 247 с.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное.

5. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988. – 128 c.

Занятие 1. Начальные понятия теории формальных языков

1. Перечислите слова языка , где и .

2. Для заданных языков L ₁ и L ₂найти .

а) , ,

б) ,

3. Пусть A ={ a, b, с }. Равны ли языки и ?

4. Для заданного языка L в алфавите A ={ a, b } найти .

а) , б) .

5. Пусть A ={ a, b, с }, и . Сколько слов содержит язык ?

6. а) Пусть A ={ a, b } и L ={ aa, ab }. Найдите L ² и L ³. Являются ли эти языки префиксными или суффиксными?

б) Пусть A ={0, 1}. Является ли префиксным или суффиксным язык L ={0, 11, 10, 01}?

7. Найдите конкатенации и языков L ₁={01, 001, 011} и L ₂={10, 100}.

8. Найдите L ², если .

9. Существуют ли такие языки L ₁ и L ₂, что языки

а) и , б) и

не равны между собой по мощности?

10. Пусть A ={ a, b } и f: – гомоморфизм.

а) Найдите , если f задан равенствами f (a)= abba и f (b)= e..

б) Найдите , если f задан равенствами f (a)= ab и
f (b)= abb.

11. Пусть f – гомоморфизм, определенный равенствами f (0)= a и f (1)= e. Найдите и .

12. Пусть f – гомоморфизм, определенный равенствами f (0)= a, f (1)= bb и f (2)= e. Опишите язык 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 ={ S ® CD,

.

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. Эквивалентны ли грамматика G ₁ с правилами P ₁ и грамматика G ₂ с правилами P ₂, если

а) , ;

б) , ?

21. Какие из данных грамматик являются эквивалентными между собой?

а) , ; ;

б) , , .

22. Найти праволинейную грамматику, эквивалентную грамматике

а) ; б) .

23. Пусть . Постройте праволинейную грамматику для языка L, если каждое слово из L

а) начинается на букву c;

б) заканчивается на букву с.

24. Постройте контекстно-свободную грамматику, порождающую

а) язык ;

б) язык ;

в) язык ;

г) язык, состоящий из всех цепочек из нулей и единиц, имеющих четное число нулей и четное число единиц,

д) язык булевых функций с переменными a, b, c, логическими операциями &, и скобками (,).

Какие из этих грамматик являются линейными?

25. Постройте порождающую грамматику для языка вещественных констант с фиксированной точкой (например, 4., -12.7, 3.14159).

26. Постройте порождающую грамматику для языка вещественных констант с плавающей точкой (например, -4.625Е-18).

Занятие 3. Конечные автоматы-преобразователи

27. Являются ли детерминированными следующие словарные функции
: {0, 1}^w®{0, 1}^w? Ответ обосновать.

а) , т.е. j:

б) s -я буква y (s) в слове равна 0, если существует
такое, что ; в противном случае .

в) s -я буква y (s) в слове равна 0, если при некотором
выполняется неравенство ; в противном случае .

28. По заданным таблицам постройте диаграммы Мура.

29. Постройте таблицы по заданным диаграммам Мура.

а) б)

30. По данным каноническим уравнениям автомата с входным алфавитом А ={0, 1} и множеством состояний Q ={0, 1} составьте таблицу и постройте диаграмму Мура.

31. Является ли словарная функция f: X*®Y*, где X=Y={0; 1}, автоматной? Если да, то постройте автомат, реализующий ее.

а) f: б) f:

в) f: г) f:

д) f: е) f:

Занятие 4. Автоматы и автоматные языки.

Date: 2015-12-13; view: 879; Нарушение авторских прав