Формальная грамматика: различия между версиями
Содержимое удалено Содержимое добавлено
→Типы грамматик: Исправлена ссылка на статью о контекстно-свободных грамматиках |
|||
Строка 114:
По [[w:иерархия Хомского|иерархии Хомского]], грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
* тип 0. [[w:неограниченные грамматики|неограниченные грамматики]] — возможны любые правила
* тип 1. [[w:контекстно-зависимые грамматики|контекстно-
* тип 2. [[w:контекстно-свободная грамматика|контекстно-свободные грамматики]] — левая часть состоит из одного нетерминала.
* тип 3. [[w:регулярная грамматика|регулярные грамматики]] — более простые, эквивалентны конечным автоматам.
| |||