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

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

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

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

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

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

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

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