Виды формальных грамматик

Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка.

Порождающие – может построить любую правильную цепочку.

Преобразующие – для любой правильной цепочки строит её отображение в виде правильной цепочки.

Формальная грамматика называется распознающей, если для любой рассматриваемой цепочки она решает, является ли эта цепочка правильной в смысле данной грамматики.

Формальная грамматика называется порождающей, если может построить любую правильную цепочку.

Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она строит её отображение в виде правильной цепочки.

Определение. Порождающей грамматикой называется четверка (V,T,P,A), где V — конечный алфавит, состоящий из символов, - подмножество терминальных символов, - выделенный нетерминальный символ, обозначающий совокупность всех порождаемых объектов; P- конечное множество правил порождения видаu→ν, где u — непустая строка нетерминальных символов, а ν — некоторая строка. Множество всех строк терминальных символов, которые можно получить применением правил порождения, называется языком. Оно является подмножеством множества — всех строк символов из T.

В приложениях к грамматике естественных языков терминальными считаются обычные слова, а символы из — есть названия частей речи и других грамматических категорий. Правила порождения здесь могут быть следующего типа А = <предложение> →<подлежащее><сказуемое> и правила подстановки типа <подлежащее> →<мальчик> и <сказуемое>→ <улыбается>. Строки терминальных символов языка являются грамматически правильными предложениями.

В языках символической логики некоторые правила порождения называются аксиомами, а другие - «правилами вывода». «Предложения», которые можно породить с помощью правил вывода и аксиом, называются теоремами рассматриваемой дедуктивной системы.

Рассмотри примеры порождающих грамматик с ,т.е. грамматик с единственной грамматической категорией.

1. Пусть и P состоит из двух правил порождения , . Эта грамматика порождает язык , т.е. Множество состоит из всех конечных строк, составленных из символа C.
2. Пусть и P состоит из следующих правил порождения:

,где∧— пустая строка, которая подчиняется правилу , т.е. она исчезает в любой непустой строке. Эта грамматика порождает пустую строку и две двоичные последовательности вида ,где , а — обращение строки .

1. Пусть и состоит из правил порождения , . Она порождает язык .
2. Пусть , а P состоит из правил порождения , , . Она порождает язык, состоящий из всех строк в, закончившихся на b.

Определение. Правило порождения называется контекстно -свободным, если оно применимо к любой строке вида и дает строку . Язык, который порождается лишь контекстно-свободными правилами, называется контекстно-свободным.

Если разрешается применять правило к строке лишь при некоторых a,b, то это правило называется зависящим от контекста. Заметим при этом, что правила естественных языков в сильной степени зависят от контекста. Искусственные языки обычно являются контекстно-свободными.