Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

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

Грамматика непосредственно-составляющих называется НС-грам­

фрагмент грамматики русского языка, заданного следующими пра­ вилами:

100

Правила /ч — F 6 — это в действительности группа правил, посколь­

вый, красивый, мяч, мальчик, девочка, потерял, ударил, бросил}.

i / H = { П , С , Г , Г, С , П } .

Начальным символом будет понятие предложения. Выводимые терминальные цепочки — правильные предложения данного, языка.

\ / /о ч

одну и ту же синтаксическую структуру фраз, что может быть вы­

ребер, каждое из которых связано с предшествующим. В лингвисти­ ке слова или последовательности, которые функционируют в ка­ честве элементов другой конструкции, называются составляющи­ ми. Отсюда название маркера структуры составляющих.

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

В рассматриваемом предложении составляющими являются — «мяч», «красивый мяч», «уронил красивый мяч», а «уронил краси­

101

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

Например, С и Г — непосредственные составляющие предложе­ ния. Есть непосредственные составляющие для С и Г — это соответ­ ственно П и С, и Г и С и т. д. Очевидно, грамматика не может счи­

Два С-маркера считаются тождественными, если они имеют оди­ наковую структуру ветвей и одинаковые метки при соответствую­ щих узлах. Дерево С-маркера характеризуется определенным упорядочением ветвей слева направо в соответствии с порядком элементов в цепочке.

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

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

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

Элемент А называется леворекурсивным, если подчиненное ему дерево содержит А только в самой левой цепи. (Дерево, подчинен­ ное А , — это дерево, которое может быть выведено из А . )

102

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

Рекурсивный элемент А называется самовставленным, если подчиненное ему дерево содержит А в некоторой внутренней цепи. Два структурных дерева тождественны, если имеют одинаковую структуру ветвей, т. е. восходящих линий от морфем языка к син­ таксическим типам, и одинаковую разметку ребер и узлов дерева.

ва x e L G все его выводы имеют одно и то же дерево.

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

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

различными способами. При этом под существенно различными вы­

бами:

1)S ~ * S 1 S ^ 0 1 S - > 0 1 S 1 S - » 0 1 0 1 S - * 0 1 0 1 0 ;

2)S - > S 1 S - » S 1 0 ^ S 1 S 1 0 - ^ 0 1 S 1 0 ~ * 0 1 0 1 0 .

ЮЗ

Им соответствуют различные структурные описания, полученные

в LG':

1) (s(sO) l ( s ( 5 0 ) 1 ( # ) ) ) ;

2)U U U O ) i u o ) ) i ( s O ) ) .

Выводы цепочки х в некотором языке LG называются существен­ но различными, если структурные описания х', соответствующие этим выводам, отличаются друг от друга.

Если заранее известно, что грамматика не является неоднознач­ ной, то, очевидно, по любой порождаемой ею цепочке можно -одно­ значно восстановить вывод этой цепочки.

Если задана конкретная грамматика G одного из типов и нуж­ но установить, является ли она неоднозначной, то алгоритмическая разрешимость такой задачи устанавливается следующей теоремой:

Теорема (12). Для языков типа 3 существует алгоритм, позво­ ляющий по заданной грамматике определить, является ли она од­

грамматику без неоднозначностей, эквивалентную заданной. В про­ тивном случае язык L называется языком без неоднозначности или однозначно выводимым.

Следующие две теоремы относятся к вопросу о существовании

^3=1} являются существенно неоднозначными. Второй из этих язы­

2 D — подкласс языков типа 2, называемый «детерминированные бесконтекстные языки».

104

Следующая теорема рассматривает алгоритмическую разреши­ мость распознавания существенной неоднозначности:

Теорема 15 (Гладкого). Не существует алгоритма для решения задачи о том, является ли заданный язык типа 2° существенно не­ однозначным. Однако в некоторых случаях этот вопрос может быть решен.

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

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

В соответствии с этим в общем случае можно рассматривать различные типы маркеров, содержащие ту или иную информацию.

105