Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы»



Скачать 13.89 Kb.
Дата27.07.2013
Размер13.89 Kb.
ТипДокументы
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы»

Специализация «Компьютерная математика»

Осенний семестр 2010 г.



  1. Языки, грамматики, распознаватели. Классы грамматик и классы языков. Иерархия Хомского. Рекурсивно перечислимые и рекурсивные языки.

  2. Контекстно-зависимые языки, их рекурсивность. Праволинейные грамматики и регулярные языки.

  3. Контекстно-свободные грамматики и языки. Вывод. Дерево вывода. Левосторонний и правосторонний вывод. Неоднозначные грамматики и языки.

  4. Достижимые и производящие символы. Теорема о приведенной грамматике.

  5. Лемма о накачке. Следствия о неКСЯ. Теорема об унарных языках и периодических множествах.

  6. Теорема о подстановке. Следствия об операциях. Следствие о длинах слов.

  7. Пересечение КСЯ. Теорема о пересечении КСЯ с регулярным языком.

  8. Теорема о λ-свободной грамматике.

  9. Теорема о нормальной форме Хомского. Алгоритм Кока-Янгера-Касами распознавания КСЯ.

  10. МП-автоматы. Принцип работы. Конфигурации. Варианты распознавания. ДМПА и НМПА, их неэквивалентность.

  11. Теорема о распознавании КСЯ при помощи НМПА.

  12. Теорема о классе языков, распознаваемых НМПА.

  13. Преобразования КС-грамматик: устранение левой рекурсии, левая факторизация.

  14. Идея синтаксического анализа. Два способа анализа. Использование МПА для нисходящего анализа. Основное тождество.

  15. Множества FIRST, FOLLOW и SELECT. Алгоритмы их построения. Построение управляющей таблицы МП-автомата. LL(1)-грамматики.

  16. Идея восходящего анализа. Основа. Свертка. Метод перенос-свертка. Основное тождество. Положение текущей основы в стеке.

  17. Схема LR-анализа. Состояния. Функции ACTION и GOTO.

  18. Активные префиксы. Пункты. Автомат пунктов, его свойства.

  19. Построение таблиц ACTION и GOTO. Конфликты. SLR-анализ.

Основной учебник:

Замятин А.П., Шур А.М. Языки, грамматики, распознаватели. Изд-во УрГУ, 2007.

elar.usu.ru/bitstream/1234.56789/1363/5/1324616_schoolbook.
pdf

Похожие:

Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconМножество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.)
Слова и языки. Конкатенация. Уравнение xy=YX. Примитивные слова. Отношение сопряженности. Сохранение примитивности. Классы сопряженности....
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к зачету/экзамену по спецкурсу «Теория неотрицательных матриц и ее приложения»
Оценки корня Фробениуса: через строчные суммы, через координаты вектора и его образа
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к зачету по спецкурсу "Математические методы принятия решений в условиях неопределенности"

Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к зачёту и экзамену по дисциплине «Экономика организации (предприятия)»
Вопросы к зачёту и экзамену по дисциплине «Экономика организации (предприятия)» для групп 2БД, 2Э, 2зио, 1зЭ
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconК лингвокультурологическому спецкурсу «история православной России»
К лингвистическому спецкурсу «Актуальные вопросы лексической семантики»
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к экзамену (зачету) по курсу Логика

Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к экзамену и зачету по дисциплине «Логика». Предмет логики

Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» icon4 Вопросы для подготовки к зачёту и экзамену 1 Вопросы для подготовки к зачету

Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к экзамену по спецкурсу «Славяноведение в России в XIX начале XX вв»
Определение славяноведения. Содержание предмета. Состояние знаний в России о зарубежных славянах в первой четверти XIX века
Вопросы к зачету/экзамену по спецкурсу «Языки и автоматы» iconВопросы к устному экзамену и зачету по «Истории отечественного и зарубежного искусства»
Архитектура и скульптура Западной Европы позднего средневековья (готический стиль)
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org