(16) Z+X+W—>Z+Y+W
Например, в том случае, когда рассматривается единственное и множественное число глаголов, мы должны вместо того, чтобы добавлять к (13) правило Verb—>hits, добавить правило
(17) NPsing+Verb —> Npsing+hits.
показывающее, что hits подставляется на место Verb только в контексте NPsing—. Соответственно, правило (13 II) должно быть сформулировано так, чтобы можно было учесть NPsing и NPpl[15]. Это прямое обобщение правила (13). Одна черта системы (13) должна быть сохранена, однако, как это имеет место в (17): при применении одного правила только один элемент может подвергаться подстановке; другими словами, в (16) X должен представлять собой один символ, например Т или Verb, а не последовательность символов, как, скажем, T+N. Если это условие не соблюдено, мы не можем надлежащим образом восстановить структуру непосредственно составляющих предложений-дериватов по соответствующим схемам вида (15) , как мы делали выше.
Теперь мы в состоянии дать более общее описание того типа грамматики, который связан с теорией лингвистической структуры, основанной на анализе по непосредственно составляющим. Всякая такая грамматика определяется конечным множеством Σ начальных цепочек и конечным множеством F «формул-команд» вида X—>Y, означающих: «подставить Y вместо X». Хотя X не обязательно должно быть одним символом, только один символ из состава X может быть заменен при образовании Y. В грамматике (13) множество Σ начальных цепочек состоит из единственного символа Sentence, a F состоит из правил (I) —(VI); но мы можем потребовать расширения множества Σ, с тем чтобы оно включало, например, Declarative Sentence, Interrogative Sentence в качестве дополнительных символов. Обладая грамматикой [Σ,F], мы определяем деривацию как конечную последовательность цепочек, начинающуюся с одной из начальных цепочек Σ, такую, что каждая цепочка в ней получается из предыдущей цепочки в результате применения одной из формул-команд множества F. Так, (14) есть деривация; пятичленная последовательность цепочек, состоящая из первых пяти строк (14),также есть деривация. Некоторые деривации являются завершенными в том смысле, что нет такого правила в F, с помощью которого можно было бы преобразовать их последнюю цепочку. Так, (14) — завершенная деривация, а последовательность первых пяти строк (14) — незавершенная. Если какая-то цепочка является последней цепочкой завершенной деривации, мы называем ее терминальной.Так, the+man+hit+the+ball есть терминальная цепочка грамматики (13). Некоторые грамматики типа [Σ,F] могут не иметь терминальных цепочек, но мы интересуемся только теми грамматиками, которые их имеют, то есть описывающими некоторые языки. Множество цепочек называется терминальным языком, если это множество является множеством терминальных цепочек некоторой грамматики [Σ,F]. Таким образом, каждая такая грамматика определяет некоторый терминальный язык (в частности, «пустой» язык, не содержащий ни одного предложения), и каждый терминальный язык порождается некоторой грамматикой типа [Σ,F], Имея терминальный язык и его грамматику, мы можем реконструировать структуру непосредственно составляющих каждого предложения этого языка (каждой терминальной цепочки грамматики), рассматривая соответствующие схемы типа (15), как мы делали это выше. Мы можем также определить грамматические отношения в этих языках формальным образом в терминах соответствующих схем.
4.2.
В § 3 мы рассмотрели языки, названные «языками с конечным числом состояний», которые порождаются посредством марковских процессов с конечным числом состояний. В настоящей главе мы рассматриваем терминальные языки, порождаемые системами вида [Σ,F]. Эти два типа языков связаны друг с другом следующим образом.
Теорема: Каждый язык с конечным числом состояний есть терминальный язык, но существуют терминальные языки, не являющиеся языками с конечным числом состояний[16]. Важно в этой теореме то, что описание в терминах модели непосредственно составляющих оказывается существенно более сильным, чем описание в терминах элементарной теории, рассмотренной выше в § 3. Примерами терминальных языков, не являющихся языками с конечным числом состояний, могут служить языки (10 I) и (10 II), рассмотренные в § 3. Так, язык (10 I), состоящий из всех цепочек вида ab, aabb, aaabbb,.. и только этого вида, может порождаться [Σ,F]-грамма- тикой (18):
15
Так, в более полной грамматике правила (13 II) можно заменить следующей совокупностью правил:
где
16
См. мою работу «Three models for the description of language» (см. выше, стр. 426, прим. 10), где приводится доказательство этой и других теорем, касающихся сравнительной силы грамматик.