Порождающие грамматики Хомского.

В 1956 г. Ноам Хомский предложил модель порождающей грамматики, которая весьма удобна для задания искусственных языков [Х62]. Одно из удобств этой модели в том, что во многих случаях каждой порождаемой цепочке языка эта модель позволяет сопоставить ее структуру. Определение 2.2. Порождающей грамматикой Хомского называется четверка объектов: G=(T,N,S,R), где: T – конечное непустое множество (терминальный словарь). Элементы T будем называть терминальными символами; N - конечное непустое множество (нетерминальный словарь). Элементы N будем называть нетерминальными символами; множества N и Т не пересекаются; S – выделенный элемент нетерминального словаря, S∈N, так называемый начальный символ; R – конечное непустое множество правил (продукций), каждое из которых имеет вид α→β, где и α, и β - цепочки над объединенным словарем T∪N. Пример 2.2. Рассмотрим следующую грамматику Хомского: G0=({a,b,c}, {S,A,B}, S, R), где: R={ S→aSbAc, aS→bbAc, bAc→B, SbA→ε, B→b }. Терминальный словарь грамматики G 0 содержит три терминальных символа (или терминала) a, b и c, нетерминальный словарь содержит три нетерминальных символа (нетерминала) A, B и начальный нетерминал S, множество R содержит пять продукций (правил). Для того, чтобы различать в цепочках терминалы от нетерминалов, обычно (если не указано противное) терминалы обозначают строчными латинскими буквами a,b,c, …, а нетерминалы – прописными латинскими буквами A,B,C, …. Цепочки символов обычно обозначаются греческими буквами α, β, γ,....При таком условии, если указать начальный нетерминал грамматики (по умолчанию будем считать начальным нетерминал S), то вся грамматика может быть задана перечислением конечного множества правил. Так, грамматика G0 может быть задана просто набором правил: G0= 1. S→aSbAc 2. aS→bbAc 3. bAc→B 4. SbA→ε 5. B →b Нумерация правил приведена здесь только для удобства ссылок на них. Рассмотрим теперь, как "работает" грамматика Хомского, каким образом можно, используя правила такой порождающей грамматики, получать цепочки языка. Во-первых, рассмотрим как из одних цепочек с помощью правил грамматики могут быть порождены другие цепочки. Это делается с помощью операции подстановки. Определение 2.3. Из цепочки α непосредственно выводима цепочка β в грамматике G (обозначается α⇒Gβ, или просто α⇒β, если грамматика G очевидна), если: - цепочку α можно представить как конкатенацию трех цепочек, α=µτν (некоторые из цепочек могут быть пустыми); - цепочку β также можно представить как конкатенацию трех цепочек, β=µξν; - в грамматике G есть продукция τ→ξ ("разрешающая" подстановку цепочки ξ вместо подцепочки τ). Символ ⇒ обозначает бинарное отношение на множестве всех цепочек над объединенным словарем TUN. Пара цепочек α и β находится в этом отношении, если α⇒β. Это стандартное обозначение бинарного отношения. Таким образом, каждая грамматика Хомского G определяет бинарное отношение ⇒G на множестве (TUN)*. Пример 2. 3. Из цепочки bAсaS в грамматике G0 можно непосредственно вывести несколько цепочек, в зависимости от того, какое правило подстановки использовать и какую подцепочку в исходной цепочке мы будем заменять. Например, bAсaS ⇒ ВaS, если по правилу 3 грамматики G 0 вхождение подцепочки bAс мы заменим на цепочку В, bAсaS ⇒ bAcbbAc, если по правилу 2 грамматики G0 вхождение подцепочки aS заменяется на цепочку bbAc, bAсaS ⇒ bAcaaSbAc, если по правилу 1 грамматики G0 заменяется вхождение подцепочки S на цепочку aSbAc. Таким образом, грамматика Хомского представляет собой, фактически, конечное число правил α→β, где символ "→" можно интерпретировать как: "можно заменить на". Так из одних цепочек с помощью правил подстановки можно получить другие цепочки - объекты той же самой природы, что и исходные объекты. Поэтому операцию непосредственной подстановки можно выполнять многократно, используя каждую следующую полученную цепочку как исходную для ее дальнейшего преобразования. Определение 2.4. Из цепочки α выводима цепочка β в грамматике G (обозначается α⇒*Gβ, или просто α⇒*β, если грамматика G очевидна), если существует конечное множество цепочек π0, π1,... πn, n≥0, такое, что α=π0, πn= β, и для любых i= 1,... n выполняется πi-1⇒πi. Иными словами, цепочка β выводима из цепочки α в грамматике G, если β можно получить из α за конечное число шагов применения операции непосредственной выводимости. Символ "⇒*" означает рефлексивное транзитивное замыкание отношения "⇒". Пример 2. 4. Из цепочки bAсaS в грамматике G 0 можно вывести несколько цепочек. Например (здесь выделены заменяемые подцепочки): bAсaS⇒*cbc, поскольку bAсaS⇒BaS⇒caS⇒cbbAc⇒cbB⇒cbc; bAсaS⇒* Baac, поскольку bAсaS⇒bAcaaSbAc⇒bAcaac⇒Baac. Таким образом, грамматика Хомского представляет собой механизм порождения одних символьных цепочек из других символьных цепочек, причем из одной и той же цепочки можно породить несколько различных цепочек, иногда бесконечное их количество. Например, в грамматике G0 цепочка bAсaS после подстановки вместо S цепочки aSbAc по первому правилу превращается в цепочку, также содержащую S. Из этой новой цепочки по тому же правилу мы опять можем породить цепочку, содержащую S, и т.д. Отметим, что порождающая грамматика Хомского не предписывает определенный единственный вывод, т.е. не задает алгоритм порождения. Здесь отсутствует важнейший элемент алгоритма – его недетерминированность. Грамматика представляет возможность, инструмент, механизм порождения цепочек, и с этой точки зрения является исчислением, подобным, например, исчислению высказываний. Действительно, в исчислении высказываний объектами, над которыми производятся операции, являются высказывания, в грамматиках Хомского - цепочки символов. Конечным множеством операций в исчислении высказываний является полное множество логических операций {импликация, отрицание}, в грамматике Хомского – правила грамматики, в соответствии с которыми осуществляются подстановки. В отличие от исчисления высказываний, в грамматике Хомского множество операций уникально для каждой грамматики. Но в обоих случаях – и в исчислении высказываний, и в грамматиках – конечные множества операций используются для получения одних объектов из других: высказываний из высказываний, цепочек из цепочек. В обоих случаях порядок применения операций, алгоритм получения новых объектов из старых не предписан, можно использовать разные операции, разные объекты, и получать разные – обычно бесконечное число – порожденных объектов. Перейдем теперь к вопросу о том, как связаны между собой порождающая грамматика Хомского и порождаемый ею язык. Как грамматика порождает язык? Определение 2.5. Языком, порождаемым грамматикой G, называется множество терминальных цепочек, выводимых из начального символа грамматики. Или, формально, L(G) = {α∈Τ | S⇒G*α}. Итак, любой вывод цепочек языка мы должны начинать только с начального нетерминального символа. Если после произвольного числа подстановок подцепочек в соответствии с правилами грамматики, полученная в результате цепочка состоит из терминалов, то это – цепочка порождаемого грамматикой языка. (Отсюда ясны названия терминальные-нетерминальные символы. Только терминальные, 'окончательные' символы могут встретиться в цепочках языка, заканчивающих вывод). Например, цепочка bbb принадлежит языку, порождаемому грамматикой G 0. Действительно: S⇒aSbAc⇒bbAcbAc⇒bBbAc⇒bBB⇒bbB⇒bbb. Пример 2.5. Попробуем охарактеризовать весь язык, который порождается грамматикой G0. Начинаться любой вывод может только с начального нетерминала, и для его замены в G0 есть только одно, первое правило: S→aSbAc. Заменять S по первому правилу можно многократно, следовательно, мы в общем случае можем получить промежуточные цепочки вывода в этой грамматике вида: S⇒* anS(bAc)n. Дальше вывод может пойти двумя путями: либо мы используем второе правило aS→bbAc, для того, чтобы заменить подцепочку аS на цепочку, не включающую S, либо по четвертому правилу подцепочка SbA будет заменена на пустую цепочку (поскольку мы используем кроме S и соседние символы, по крайней мере один шаг в выводе должен быть сделан, т.е. n>0). В первом случае имеем: S⇒* anS(bAc)n = an-1aS(bAc)n ⇒an-1bbAc(bAc)n⇒* an-1bBn+1⇒*an-1b n+2. Во втором: S⇒* anS(bAc)n = anSbAc(bAc)n-1 ⇒anc(bAc)n-1⇒* anсBn-1⇒*ancb n-1. Легко видеть, что никакие другие выводы из S в G0 невозможны. Окончательно, L0=L(G0)={ an-1b n+2, ancb n-1  n>0 }.