3. Основы теории формальных языков и грамматик. Основные понятия и определения. Операции над языками. Классификация формальных языков и грамматик по порождающей способности

Определение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I> О VA, R },

где Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой;

VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;

<I> - начальный символ грамматики <I> О VA.

R - множество правил вывода или порождающих правил вида a ® b , где aи b - цепочки , построенные из букв алфавита VтИ VA, который называют полным алфавитом (словарем) грамматики Г.

Определение. Множество конечных цепочек терминального алфавита Vт грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L( Г).

Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем или алфавитом, а символы, входящие в множество, - буквами алфавита.

Определение. Пусть r = t ® g - правило грамматики Г и a = c't c" - цепочка символов, причем c', c" О(Vт ИVA) *. Тогда цепочка b= c' g c " может быть получена из цепочки путем применения правила r (т.е. заменой в m цепочки t на g). В этом случае говорят, что цепочка b непосредственно выведена из цепочки a и обозначают a Юb .

Типы формальных языков и грамматик

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

Грамматики типа 0, которые называют грамматиками общего вида, не имеют никаких ограничений на правила порождения (ЕЯ). Любое правило r = h ® y может быть построено с использованием произвольных цепочек h, y О (Vт И Va)*. Например,

<T><W> ® <W><T> или x<A>b<C><D> ® x<H><D>

Грамматики типа 1, которые называют также контекстно-зависимыми грамматиками,не допускают использования любых правил. Правила вывода в таких грамматиках должны иметь вид: c1<A>c2 ® c1w c2, где c1, c2 - цепочки, возможно пустые, из множества (Vт И Va)*, символ <А> О Va и цепочка w О (Vт И Va)*. Цепочки c1 и c2 остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно зависимой.

Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками ( КС-грамматики или Б-грамматики). Правила вывода таких грамматик имеют вид: <A> ® a, где <A> О Va и a О (Vт И Va)*. Очевидно, что эти правила получаются из правил грамматики типа 1 при условии c1 = c2 = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования.

Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид: <A> ® a или <A> ® a<B> или <A> ® <B> a, где a О Vт, <A>, <B> О Va, причем грамматика может иметь только правила вида <A> ® a<B> - правосторонние правила, либо только вида <A> ® <B>a - левосторонние правила.

Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

Билет 19