ta / ТА. Список вопросов к экзамену и зачету (2014)

Вопросы к экзамену и зачету по курсу “ Теория автоматов” для групп K04-121,122,123 и Б04-04Б

1.Предмет изучения теории автоматов: абстрактно-алгебраическая теория автоматов.

2.Предмет изучения теории автоматов: структурная теория автоматов.

3.Предмет изучения теории автоматов: теория вероятностных автоматов и самоорганизующихся систем.

4.Применение теории автоматов в программных и аппаратных системах.

5.Генераторы конечных автоматов. Примеры и принципы использования.

6.Теория автоматов и теория компиляторов: понятие компилятора и интерпретатора. Этапы

ифазы работы компилятора: лексический, синтаксический, семантический анализ.

7.Теория автоматов и теория компиляторов: понятие компилятора и интерпретатора. Этапы

ифазы работы компилятора: оптимизация и кодогенерация.

8.Лексический анализ: основные задачи, структура лексического анализатора. Понятие и структура таблицы символов.

9.Основные понятия лексического анализа: токены и их атрибуты, шаблоны, лексемы. Принцип выборов токенов.

10.Основные лингвистические определения. Операции над языками.

11.Регулярные выражения. Законы преобразования регулярных выражений.

12.Понятие регулярного определения. Расширенные операции над регулярными выражениями.

13.Классификация автоматов. Детерминированные и недетерминированные конечные автоматы. Автоматы с памятью, магазинные автоматы. Способы задания автоматов.

14.(*) Алгоритм Мак-Нотона-Ямады-Томпсона. Свойства алгоритма.

15.(*) Преобразование ДКА в НКА: понятие ε-замыкания, алгоритм построения подмножеств.

16.(*) Понятие минимального ДКА, единственность минимального ДКА, алгоритм минимизации состояний ДКА.

17.(*) Алгоритм непосредственного преобразования регулярного выражения в ДКА.

18.(*) Алгоритмы преобразования ДКА в регулярное выражение: алгоритм K-Path-алгоритм.

19.(*) Алгоритмы преобразования ДКА в регулярное выражение: алгоритм исключения состояний.

20.Элементы структурной теории автоматов: автоматы Мили и Мура.

21.Элементы структурной теории автоматов: канонический метод структурного синтеза произвольных автоматов.

22.Элементы структурной теории автоматов: базовые логические элементы; методы минимизации булевых функций.

23.Элементы структурной теории автоматов: элементы памяти, основные триггеры: D, Т, JKтриггеры; триггеры с произвольными входами и функциями переключения.

24.Элементы структурной теории автоматов: подходы к синтезу автоматов Мили и Мура.

25.Элементы структурной теории автоматов: формальные методы оценки качества синтеза автоматов (количество состояний, задержки и т.п.)

26.Классы языков и их свойства: свойства разрешимости и свойства замкнутости. Способы представления языков.

27.Свойства регулярных языков и алгоритмы для их проверки: принадлежность к языку, пустота языка, бесконечность языка.

28.Лемма о накачке для регулярных языков. Применение леммы.

29.Свойства регулярных языков и алгоритмы для их проверки: свойство эквивалентности и свойства включения.

30.Свойства регулярных языков и алгоритмы для их проверки: свойство замкнутости относительно объединения, пересечения и разности.

31.Свойства регулярных языков и алгоритмы для их проверки: свойство замкнутости относительно конкатенации, замыкания Клини.

32.Свойства регулярных языков и алгоритмы для их проверки: свойство замкнутости относительно инверсии, гомоморфизма и инверсного гомоморфизма.

33.Генераторы лексических анализаторов. Примеры и принципы использования.

34.Автоматы с магазинной памятью: определение, примеры использования, приемы синтеза.

35.Понятие грамматики, сентенциальной формы, предложения языка.

36.Классификация грамматик по Хомскому.

37.Способы задания грамматик. Форма Бакуса-Наура.

38.Задачи распознавания, разбора; определение дерева разбора (синтаксического дерева), понятие левых и правых порождений.

39.Неоднозначность языков и грамматик.

40.Упрощение грамматик: понятие полезности грамматических символов, устранение непорождающих и нетерминалов и недостижимых символов.

41.Упрощение грамматик: ε-продукции в грамматиках, понятие зануляемых символов, алгоритм исключение ε-продукции, алгоритм исключения единичных продукций.

42.Нормальная форма Хомского для контекстно-свободной грамматики. Алгоритм преобразование грамматики к НФХ.

43.Алгоритм Кока-Янгера-Касами. Оценка сложности алгоритма.

44.Методы разбора: общая характеристика восходящего и нисходящего разбора.

45.Общий метод разбора при помощи рекурсивного спуска.

46.(*) Проблема леворекурсивных грамматик. Алгоритм устранения левой рекурсии.

47.(*) Неоднозначности при нисходящем разборе. Алгоритм левой факторизации.

48.(*) Восходящий разбор: используемый тип порождения, понятие основы, синтаксический анализ перенос-свертка (ПС): общая характеристика, идея разбора.

49.(*) LR(0) – автомат: понятие LR(0) – пункта, семантика пункта; понятие множеств пунктов

50.(*) Построение канонического набора множеств: алгоритм построения замыкания для множества пунктов, алгоритм построения функции переходов между множествами пунктов. построение канонического набора множеств пунктов; диаграмма состояний LR(0)-автомата.

51.(*) Модель LRанализатора: понятие конфигурации, синтаксические таблицы, основные операции. Алгоритм LR(0)-анализа.

52.(*) Построение синтаксических таблиц для LR(0)-анализатора: алгоритм построения множества первых символов и алгоритм построения множества последующих символов.

53.(*) Построение синтаксических таблиц для LR(0)-анализатора: алгоритм построение таблиц SLR-анализа.

54.(*) Использование неоднозначных грамматик при восходящем разборе. Типы конфликтов при SLR-анализе и методы их разрешения при использовании неоднозначных грамматик.

55.(*) Восстановление после ошибок при синтаксическом анализе. Примеры функций восстановления после ошибок для восходящего анализатора.

56.(*) Нисходящий разбор: определение LL(1)-грамматики, алгоритм построение таблицы предиктивного анализа.

57.Лемма о накачке для контекстно-свободных языков. Применение леммы

58.Свойства контекстно-свободных языков и алгоритмы для их проверки: принадлежность к языку, пустота языка, бесконечность языка.

59.Свойства контекстно-свободных языков и алгоритмы для их проверки: свойство замкнутости относительно конкатенации, замыкания Клини.

60.Свойства контекстно-свободных языков и алгоритмы для их проверки: свойство замкнутости относительно инверсии, гомоморфизма и инверсного гомоморфизма.

61.Свойства контекстно-свободных языков и алгоритмы для их проверки: проблема неразрешимости свойств эквивалентности и включения, доказательства отсутствия свойств замкнутости относительно пересечения и разности.

62.Некоторые специальные виды грамматик. Грамматики для анализа естественных языков: грамматика структуры фразы, вероятностные контекстно-свободные грамматики.

63.Генераторы синтаксических анализаторов. Примеры и принципы использования.

Вопросы, отмеченные символом (*), вошли в контрольные работы №1 и №2 и не будут включены в основную сдачу экзамена, но будут на пересдаче (зачета и экзамена).