Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
= 12 І для і.екоторого .......im, X1,..., хт,
z = X1. . . хт и для всгх k, I k т, T имеет правило [е, Si^ г) -»¦ (Si^ , хк),где I0 = і и іт = /). (55)
Формальные свойства грамматик
201
Очевидно, что Qij регулярен. Следовательно, мы мсшем к G' добавить правила, которые дают соотношения
для всех i, j и всех х ? Q1J. Расширенная таким образом грамматика G' порождает язык TlL(G)]. Следовательно, теорема 31 верна без ограничения, наложенного на Т.
Другие результаты, касающиеся эффекта применения различных операций к бесконтекстным языкам и относящимся к ним системам, см. в работах [21, 69].
Будем теперь рассматривать правила только следующих видов:
Напомним, что нормальная грамматика содержит только правила типа а) и г); линейная грамматика без ограничения общности может быть описана как грамматика, содержащая только правила вида
б), в) и г); конечный автомат содержит только правила вида б), г) или только правила вида в) и г). Напомним также, что нормальная грамматика может порождать любой бесконтекстный язык и что линейная грамматика, хотя и с более ограниченной порождающей способностью, может порождать языки, лежащие за пределами возможностей конечных автоматов (теорема 16). Таким образом, мы получаем порождающую способность, большую, чем у конечных автоматов, разрешая лево- и право-линейные правила, и еще большую, разрешая появление нелинейных правил в грамматике. Конечно, некоторые линейные грамматики могут порождать только регулярные языки, хотя ни' в том, ни в другом случае не существует алгоритма, определяющего, когда это верно (теорема 25). Остается решить вопрос, при каких условиях нормальная или линейная грамматика богаче, чем любой конечный автомат, в отношении порождающей способности.
Чтобы изучить этот вопрос, полезно снова рассмотреть классификацию рекурсивных элементов, данную в разд. 3 предыдущей главы. Конечный автомат содержит либо все право-рекурсивные, либо все лево-рекурсивные элементы. Линейная грамматика может содержать одновременно лево-рекурсивные и право-рекурсив-ные элементы. Кроме того, и линейные, и нормальные грамматики могут содержать самовставляемые элементы. Оказывается, что последнее свойство влияет на увеличение порождающей способности по сравнению с конечными автоматами.
15 Заказ № 563
(Si, q, Sj)-+е и (S11 q, Sj) ^x
(56)
а) А-+ВС,
б) А -*¦ аВ (право-линейное),
в) А-+Ba (лево-линейное).
г) А-+а.
(57)
202
Н. Хомский
Определение 8. Грамматика называется грамматикой с самовставлением, если она содержит нетерминальный символ А, такой, что для некоторых непустых цепочек <р, A-^fAf.
Другими словами, грамматика с самовставлением содержит са-мовставляемые элементы. Теперь можно показать, что:
Если G — бесконтекстная грамматика без самовставления, порождающая L(G), то существует конечный автомат, который порождает L(G). (58)
Отсюда мы немедленно получаем следующий результат.
T е о р е м а 33. Язык L не является регулярным тогда и только тогда, когда все его бесконтекстные грамматики являются грамматиками с самовставлением [4, 8, 9].
Таким образом, L является регулярным языком только в том случае, если он обладает грамматикой без самовставления.
Ясно, что существует алгоритм, определяющий, содержит ли бесконтекстная грамматика самовставляемые элементы (аналогично содержит ли она право-рекурсивные и лево-рекурсивные элементы). Если мы испытаем грамматику G и обнаружим, что она не имеет самовставляемых символов, то мы можем заключить, что G имеет «мощность» конечного автомата (хотя она может содержать и ле-во-рекурсивные, н право-рекурсивные символы).
Если, с другой стороны, мы обнаружим, что G имеет самовставляемые символы, мы не будем знать, обладает ли оиа мощностью конечного автомата. Это зависит от ответа на вопрос, существует ли грамматика G', которая порождает тот же язык, что н G1 но не имеет самовставляемых символов.
Как мы видели, не существует механической процедуры, с помощью которой это может быть установлено для произвольной грамматики G. Таким образом, хотя теорема 33 дает эффективное достаточное условие эквивалентности бесконтекстной грамматики конечному автомату в отношении порождающей способности (и более того, условие, которому удовлетворяет некоторая грамматика каждого регулярного языка), мы знаем, что оно не может быть усилено до эффективного критерия, т. е. эффективного необходимого и достаточного условия.
Утверждение (58) непосредственно следует из элементарных свойств конечного автомата. Предположим, что G является грамматикой без самовставления, порождающей L(G), а нетерминальные элементы G суть A1,...,An. Назовем G сильно связной, если для каждых i, j существуют цепочки 9 и 1>, такие, что Л(—Предполо-
Формальные свойства грамматик
203
жнм, что G — сильно связная грамматика. Если существуют i,j, k, I, такие, что Al-^f1Ayf2 и где <?1фе+^г, тогда
немедленно получаем вопреки предположению, что G обладает свойством самовставления. Следовательно, таких i, /, k, I не существует, и, таким образом, либо каждое нетерминальное правило в G право-линейио, либо каждое правило лево-линейно. В любом случае G порождает регулярный язык.
