Cтраница 2
Выше уже отмечалось, что один и тот же язык может быть порожден грамматиками разных типов. Грамматика типа 2 ( бесконтекстная или контекстно-свободная грамматика) проще, чем контекстно-зависимая грамматика типа 1 и работать с ней во многих случаях удобней. [16]
Грамматики Хомского ( называемые также грамматиками структуры фразы) делятся на четыре типа с номерами от 0 до 3 в порядке убывания их общности. Наименее общими являются регулярные грамматики. Эквивалентные им акцепторы - конечные автоматы. На втором уровне общности находятся КС-грамматики и стековые автоматы. Этажом выше - грамматики типа 1 ( чувствительные к контексту) и линейно ограниченные автоматы. [17]