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

Решение задач 1-5 в word

-

Вариант индивидуального задания №8:

1. Пусть грамматика Хомского определяется правилами:
S→0A0 | 1B1 | BB
A→C | EeA
B→S | A
C→S | ε | CE
E→CE | a
К какому классу грамматик Хомского она относится? Постройте несколько терминальных цепочек языка, порождаемого этой грамматикой. Попробуйте сформулировать более простую (узкую) эквивалентную грамматику для порождения этого языка.
Отобразите данную грамматику с помощью иного метода задания (БНФ-нотации, язык синтаксических диаграмм, грамматики с рассеянным контекстом)
2. Определите, к какому типу относится данная грамматика, и какой язык порождает (представить в виде регулярного выражения):
S→0A1 | 01
0A→00A1
A→01
3. Допустим, структура условного оператора языка программирования с несколькими условиями имеет вид:
if условие 1 than операторы 1
elsif условие 2 than операторы 2
elsif условие 3 than операторы 3
.........
else операторы end
Постройте грамматику, описывающую структуру такой записи.
4. Дана грамматика, определяемая правилами
S→aQb | accb
Q→cSc
и порожденная терминальная цепочка acacaccbcbcb. Восстановите дерево вывода этой цепочки (левосторонний вывод, нисходящий распознаватель)
5. Постройте регулярную грамматику, которая позволяет порождать цепочки над алфавитом (a,b), в которых символ а НЕ встречается два раза подряд.
Представьте полученную грамматику в виде блок-схемы алгоритма формирования правильных цепочек языка и эквивалентного конечного автомата.
Промоделируйте работу конечного автомата, убедитесь в корректности его работы на нескольких тестовых последовательностях.
Постройте распознаватели грамматики на основе автомата с магазинной памятью и на базе машины Тьюринга. Промоделируйте работу распознавателей с помощью уже использованных тестовых последовательностей и убедитесь в корректности их работы.