Работа выполнена профессионально, на 100 баллов из 100! Спасибо!
Информация о работе
Подробнее о работе
Теория автоматов и формальных языков Вариант 4
- 14 страниц
- 2020 год
- 8 просмотров
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
-
решение в word
Вариант индивидуального задания №4:
1. Пусть грамматика Хомского определяется правилами:
S→AB
AB→aABB
B→b
A→a
К какому классу грамматик Хомского она относится? Постройте несколько терминальных цепочек языка, порождаемого этой грамматикой. Попробуйте сформулировать более простую (узкую) эквивалентную грамматику для порождения этого языка.
Отобразите данную грамматику с помощью иного метода задания (БНФ-нотации, язык синтаксических диаграмм, грамматики с рассеянным контекстом)
2. Определите, к какому типу относится данная грамматика, и какой язык порождает (представить в виде регулярного выражения):
S→bQd | ε
Q→aSa
3. Постройте КС-грамматику с начальным нетерминалом Book, описывающую структуру книги. Любая книга состоит из содержания, оглавления и нескольких глав. Каждая глава состоит из разделов, разделы – из параграфов, параграфы из предложений.
4. Дана грамматика, определяемая правилами
S→(S˅S) | (S&S)
S→˥S | a | b | c
и порожденная терминальная цепочка ((˥a&b)˅(a&c)). Восстановите дерево вывода этой цепочки (левосторонний вывод, нисходящий распознаватель)
5. Постройте грамматику, которая позволяет порождать язык
L={anbm | n≠m, n,m ≥ 0}.
Представьте полученную грамматику в виде блок-схемы алгоритма формирования правильных цепочек языка и эквивалентного конечного автомата.
Промоделируйте работу конечного автомата, убедитесь в корректности его работы на нескольких тестовых последовательностях.
Постройте распознаватели грамматики на основе автомата с магазинной памятью и на базе машины Тьюринга. Промоделируйте работу распознавателей с помощью уже использованных тестовых последовательностей и убедитесь в корректности их работы.
1 Карпов, Ю. Г.Теория автоматов [Текст] : учебник / Ю. Г. Карпов. - М. и др. : Питер, 2003. - 206 с.
2 Молчанов, А. Ю. Системное программное обеспечение: лабораторный практикум/ А. Ю. Молчанов. - СПб.: ПИТЕР, 2005. - 283 с.
3 Сольницев, Р. И. Информационные технологии в проектировании: учебное пособие/ Р.И.Сольницев; С.-Петерб. гос. ун-т аэрокосм. приборостроения. - 2-е изд.. - СПб.: ГОУ ВПО "СПбГУАП", 2007. - 56 с.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
