Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка.
Порождающие – может построить любую правильную цепочку.
Преобразующие – для любой правильной цепочки строит её отображение в виде правильной цепочки.
Формальная грамматика называется распознающей, если для любой рассматриваемой цепочки она решает, является ли эта цепочка правильной в смысле данной грамматики.
Формальная грамматика называется порождающей, если может построить любую правильную цепочку.
Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она строит её отображение в виде правильной цепочки.
Определение. Порождающей грамматикой называется четверка (V,T,P,A), где V — конечный алфавит, состоящий из символов, - подмножество терминальных символов,
- выделенный нетерминальный символ, обозначающий совокупность всех порождаемых объектов; P- конечное множество правил порождения видаu→ν, где u — непустая строка нетерминальных символов, а ν — некоторая строка. Множество
всех строк терминальных символов, которые можно получить применением правил порождения, называется языком. Оно является подмножеством
множества — всех строк символов из T.
В приложениях к грамматике естественных языков терминальными считаются обычные слова, а символы из — есть названия частей речи и других грамматических категорий. Правила порождения здесь могут быть следующего типа А = <предложение> →<подлежащее><сказуемое> и правила подстановки типа <подлежащее> →<мальчик> и <сказуемое>→ <улыбается>. Строки терминальных символов языка являются грамматически правильными предложениями.
В языках символической логики некоторые правила порождения называются аксиомами, а другие - «правилами вывода». «Предложения», которые можно породить с помощью правил вывода и аксиом, называются теоремами рассматриваемой дедуктивной системы.
Рассмотри примеры порождающих грамматик с ,т.е. грамматик с единственной грамматической категорией.
- Пусть
и P состоит из двух правил порождения
,
. Эта грамматика порождает язык
, т.е. Множество
состоит из всех конечных строк, составленных из символа C.
- Пусть
и P состоит из следующих правил порождения:
,где∧— пустая строка, которая подчиняется правилу
, т.е. она исчезает в любой непустой строке. Эта грамматика порождает пустую строку и две двоичные последовательности вида
,где
, а
— обращение строки
.
- Пусть
и
состоит из правил порождения
,
. Она порождает язык
.
- Пусть
, а P состоит из правил порождения
,
,
. Она порождает язык, состоящий из всех строк в,
закончившихся на b.
Определение. Правило порождения называется контекстно -свободным, если оно применимо к любой строке вида
и дает строку
. Язык, который порождается лишь контекстно-свободными правилами, называется контекстно-свободным.
Если разрешается применять правило к строке
лишь при некоторых a,b, то это правило называется зависящим от контекста. Заметим при этом, что правила естественных языков в сильной степени зависят от контекста. Искусственные языки обычно являются контекстно-свободными.