5.2. Грамматики непосредственно составляющих

Грамматики непосредственно составляющих относятся к классу неукорачивающих грамматик.

Неукорачивающие грамматики – грамматики, у которых для любого правила вида: j à y справедливо соотношение |j| £ |y| .

Примером неукорачивающей грамматики может служить грамматика

G=(Vт, Vн,P,S),

где Vт={a, b};

Vн={S};

P={F1, F2, F3, F4};

F1: Sàaa F3: SàaSa,

F3: Sàbb F4: SàbSb.

Пусть дано слово bSb. В результате подстановки любого из четырех правил мы получим новое слово, длина которого не меньше длины исходного словаря: baab, bbbb, baSab, bbSbb.

Грамматики непосредственно составляющих (НС-грамматики) – грамматики с правилами вида:

jАyàjwy или Аàw,

где А – нетерминальный символ,

w - произвольная непустая цепочка.

Таким образом, в НС – грамматиках на каждом шаге вывода можно заменить только один символ.

Очевидно, что НС – грамматика является неукорачивающей.

Шаг вывода в неукорачивающей грамматике, состоящей в одновременной замене нескольких символов, может быть разбит на несколько шагов, каждый из которых осуществляет замену только одного символа, т. е. для любой неукорачивающей грамматики может быть построена эквивалентная ей НС – грамматика.

Пусть в неукорачивающей грамматике имеет место правило вида:

ABàBA, где A и B – нетерминальные символы.

Такое правило может быть заменено четырьмя правилами НС – грамматики:

ABà1B;

1Bà12;

12àB2;

B2àBA,

где 1,2 – новые нетерминальные символы, которые не встречались ни в каких старых правилах.

Последовательное применение этих правил равносильно применению правила АВàВА, причем такая замена не может привести к появлению “лишних” выводов, поскольку символы 1 и 2 – новые.

Языки, порождаемые НС – грамматиками называются НС – языками.

По используемому контексту грамматики могут быть классифицированы следующим образом:

где А – нетерминальный символ,

j и w - цепочки в алфавите V = Vт ÚVн

Язык, порожденный левоконтекстной грамматикой G, будем называть левоконтекстным языком L(G); язык, порожденный правоконтекстной грамматикой G’, будем называть правоконтекстным языком L(G’).

По правилам использования контекста НС- грамматики могут иметь следующую классификацию:

где а Î V.

Для изучения свойств НС – грамматик рассмотрим маленький фрагмент грамматики русского языка, заданного следующими правилами:

F1: ;

F2: ;

F3: ;

F4: (маленький, шаловливый, красивый);

F5: (мяч, мальчик);

F6: (потерял, ударил, бросил);

F4 - F6 – группа правил, так как указывают некоторые возможности для символа П , С, Г.

Vт – {маленький, шаловливый, красивый, мяч, ударил, бросил}.

Vн – ,

- группа глагола,

- группа существительного,

Г – глагол, С – существительное, П – прилагательное, - предложение.

Начальный символ – понятие предложения.

Выводимые терминальные цепочки – правильные предложения данного языка.

Все терминальные цепочки имеют одну и ту же синтаксическую структуру фраз, что может быть выражено с помощью структурного дерева – маркера структуры составляющих (С - маркера ). В нашем примере это выглядит так:

Структурное дерево(C-маркер) – это помеченный граф (помеченные ребра и узлы), где узлам соответствуют грамматические типы или синтаксические единицы, а ребра различаются своим порядковым номером.

Каждый С – маркер содержит в виде меток при конечных узлах перечень слов, из которых составлено данное предложение.

В рассматриваемом предложении составляющими являются – “мяч”, “красивый мяч”, “уронил красивый мяч”, а “уронил красивый” – не является составляющей.

Каждая составляющая возводится к некоторому узлу дерева. Если этот узел, допустим, помечен С, то говорят, что составляющая принадлежит типу С.

Те составляющие, из которых конструкция непосредственно образована, являются непосредственными составляющими.

Например, и - непосредственные составляющие предложения. Для - это П и С, для - и и т. д.

Грамматика должна обеспечивать С – маркером каждое из бесконечного числа предложений.

Два С – маркера тождественны, если они имеют одинаковую структуру ветвей и одинаковые метки при соответствующих узлах.

Дерево С – маркера характеризуется определенным упорядочиванием ветвей слева направо в соответствии с порядком элементов в цепочке.

Поскольку число правил грамматики конечно, а число маркеров бесконечно, то могут найтись такие символы грамматического словаря, которые повторяются в С-маркерах сколь угодно много раз. Могут найтись также такие ветви дерева (то есть последовательность ребер, каждое из которых связано с предыдущим), которые содержат некоторый символ более чем n раз для любого фиксированного n.

Синтаксический элемент называется рекурсивным элементом, если для некоторого фиксированного n найдется структурное дерево, цепь которого содержит этот символ как наименование узла более чем n раз.

Выделяются три вида рекурсивных элементов:

Элемент А- самовставленный, то есть подчиненное ему дерево содержит А во внутренней цепи.

Грамматика G = (VT, VH, S,P) называется грамматикой с самовставлением, если для некоторого AÎ VH существует вывод АÞjАy, где j и y - непустые слова в V.

Предлагаю ознакомиться с аналогичными статьями: