Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Теория автоматов и формальных языковСтр 1 из 3Следующая ⇒ ОСНОВНАЯ ЛИТЕРАТУРА 1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1: Синтаксический анализ. М.: Мир, 1978. – 612 с. 2. Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. – 528 с. 3. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учебное пособие. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 247 с. 4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное. 5. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988. – 128 c. Занятие 1. Начальные понятия теории формальных языков 1. Перечислите слова языка , где и . 2. Для заданных языков L 1 и L 2найти . а) , , б) , 3. Пусть A ={ a, b, с }. Равны ли языки и ? 4. Для заданного языка L в алфавите A ={ a, b } найти . а) , б) . 5. Пусть A ={ a, b, с }, и . Сколько слов содержит язык ? 6. а) Пусть A ={ a, b } и L ={ aa, ab }. Найдите L 2 и L 3. Являются ли эти языки префиксными или суффиксными? б) Пусть A ={0, 1}. Является ли префиксным или суффиксным язык L ={0, 11, 10, 01}? 7. Найдите конкатенации и языков L 1={01, 001, 011} и L 2={10, 100}. 8. Найдите L 2, если . 9. Существуют ли такие языки L 1 и L 2, что языки а) и , б) и не равны между собой по мощности? 10. Пусть A ={ a, b } и f: – гомоморфизм. а) Найдите , если f задан равенствами f (a)= abba и f (b)= e.. б) Найдите , если f задан равенствами f (a)= ab и 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 1 с правилами P 1 и грамматика G 2 с правилами P 2, если а) , ; б) , ?
21. Какие из данных грамматик являются эквивалентными между собой? а) , ; ; б) , , .
22. Найти праволинейную грамматику, эквивалентную грамматике а) ; б) . 23. Пусть . Постройте праволинейную грамматику для языка L, если каждое слово из L а) начинается на букву c; б) заканчивается на букву с.
24. Постройте контекстно-свободную грамматику, порождающую а) язык ; б) язык ; в) язык ; г) язык, состоящий из всех цепочек из нулей и единиц, имеющих четное число нулей и четное число единиц, д) язык булевых функций с переменными a, b, c, логическими операциями &, и скобками (,). Какие из этих грамматик являются линейными? 25. Постройте порождающую грамматику для языка вещественных констант с фиксированной точкой (например, 4., -12.7, 3.14159). 26. Постройте порождающую грамматику для языка вещественных констант с плавающей точкой (например, -4.625Е-18).
Занятие 3. Конечные автоматы-преобразователи
27. Являются ли детерминированными следующие словарные функции а) , т.е. 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. Автоматы и автоматные языки.
|