Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





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

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 и
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 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. Являются ли детерминированными следующие словарные функции
: {0, 1}w®{0, 1}w? Ответ обосновать.

а) , т.е. j:

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

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

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

 

 


 

а) x (t) z (t -1) y (t) z (t)
    q 0   q 1
    q 0   q 2
    q 1   q 0
    q 1   q 3
    q 2   q 1
    q 2   q 3
    q 3   q 0
    q 3   q 2

 


 

б) A Q F H
    q 0   q 1
    q 0   q 1
    q 1   q 2
    q 1   q 3
    q 2   q 0
    q 2   q 3
    q 3   q 1
    q 3   q 3

 

 


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: 753; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию