U x|y|z. U ::= x|y|z. {левая часть } >= N 1. U=x. 2. U=y. 3. U=z. 5-1

Убывание мощности Сложность реализации Формальные грамматики Контектсно- зависимая грамматика (КЗ-грамматика) Грамматика с фразовой структурой (неограниченная) Регулярная или автоматная грамматика Контектсно- свободная грамматика (КС-грамматика) Тип 0 Тип 1 Тип 2 Тип 3 Классификация Хомского (иерархия Хомского) 5-2

Тип 0 Тип 1 Тип 2 Тип 3 Автоматная грамматика 5-3 КС- грамматика Ограничения на правила грамматики

Задача вывода: Пусть дана формальная грамматика: G= Р: 1. Пр=ПС. 2. П=ИС|М. 3. С=ГФ. Пр – предложение 4. ИС= кошка|собака. П – подлежащее 5. М=он. С – сказуемое 6. ГФ=идет|лежит. ИС – имя существительное М – местоимение ГФ – глагольная форма 1. Пр П С ИС С кошка С кошка ГФ кошка лежит 2. Пр П С П ГФ П лежит ИС лежит кошка лежит Пр | П С / \ | ИС М ГФ | / \ он идет лежит кошка собака 5-4

Интерпретация КА 5-5

Матрица связности

ПереходНКА ДКА ДКА- детерминированный конечный автомат НДКА- недетерминированный конечный автомат 5-7