Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Лемма 4.7. Существует алгоритм, позволяющий по любой Ъ-грамматике Г и любому ее вспомогательному символу А распознать, является ли А бесплодным.
Доказательство. Пусть T={V,W,I,R)— Б-грамматика, и для некоторого символа A ^.W существуют выводы, начинающиеся данным символом и заканчивающиеся цепочками в V. Возьмем тот из этих выводов, чье дерево — обозначим его То — содержит меньше всего узлов (если такое дерево не одно, то берем любое). Дерево То будет простым. В самом деле, если это не так, то в нем найдется путь 61, 62, ..., бг такой, что 61 и бг помечены одним и тем же символом и бг — невисячий узел; но тогда дерево Sub (Го, Г', Г"), где V и Т" — полные 61- и бг-поддеревья То соответственно, будет содержать меньше узлов, чем Го, и тоже будет деревом вывода, начинающегося символом А и заканчивающегося цепочкой в V. По лемме 4.5 высота Г0 не превышает ц(№), откуда по лемме 4.4 можно найти верхнюю границу для длины соответствующего вывода. Искомый алгоритм состоит, таким образом, в переборе всех выводов в Г, длины которых не превосходят этой границы.
Поскольку бесплодность начального символа Б-грамматики означает пустоту порождаемого ею языка, из леммы 4.7 вытекает
Теорема 4.1. Существует алгоритм, позволяющий по любой Ъ-грамматике Г распознать, является ли язык ЦГ) пустым.
Пусть Г =(V, W, I, R)— Б-грамматика и Сим-
вол А е W мы будем называть Z- б есплодным, если из него не выводима никакая цепочка в словаре Z. Буквальным повторением рассуждений, примененных при доказательстве леммы 4.7, получается
Лемма 4.7'. Существует алгоритм, позволяющий по любой Ъ-грамматике T—{V,W,I,R), любому словарю Z<=,V и любому символу А е W распознать, является ли А Z-бесплодным.
§ 4.2] РАСПОЗНАВАНИЕ ПУСТОТЫ И КОНЕЧНОСТИ Б-ЯЗЫКА 123
Назовем вспомогательный символ Б-грамматики Г неустранимым, если он а) зависит от начального символа или совпадает с ним и б) не бесплоден. В противном случае вспомогательный символ будет называться устранимым. Б-грамматику, все вспомогательные символы которой неустранимы, будем называть приведенной.
Лемма 4.8. Для всякой Б-грамматики Г = = (V, W,I,R), порождающей непустой язык, можно построить эквивалентную ей приведенную Ъ-грамматику Г ~{V,W',I,R') такую, что W' ? W и R'^R.
Доказательство. Из определения ясно, что ни один узел дёрева полного вывода не может быть помечен устранимым вспомогательным символом. Поэтому, выбросив из вспомогательного словаря все устранимые символы, а из схемы — все правила, содержащие эти символы в левых или правых частях, мы не изменим порождаемого грамматикой языка. Полученная так грамматика не обязана еще быть приведенной*), но в случае надобности к ней можно применить такое же преобразование, затем так же преобразовать следующую грамматику и т. д. Этот процесс когда-нибудь оборвется, так как на каждом шаге мощность вспомогательного словаря уменьшается. Поскольку язык L(T) не пуст, в описанном процессе никогда не будет выброшен начальный символ, и в конце концов получится приведенная грамматика, эквивалентная Г.
Будем теперь называть вспомогательный символ Б-грамматики циклическим, если он зависит от самого себя. Имеет место
Лемма 4.9. Приведенная Ъ-грамматика без правил вида А—* В, где А и В — вспомогательные символы, тогда и только тогда порождает бесконечный язык, когда хотя бы один ее вспомогательный символ является циклическим.
Доказательство. 1) Пусть Г — данная грамматика и А — циклический вспомогательный символ. Тогда
*) Символ, неустранимый в старой грамматике, может стать устранимым в новой. Например, в грамматике Г = ({а}, {/, А, В), 1, I -*? АВ, А -*? а}) устранимым символом является только В,
но после изъятия этого символа и правила / -*? АВ символ А тоже становится устранимым.
124 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
Существуют такие цепочки ср и г]з, что A Ь- фЛг|>, откуда
Г
для любого п — 1, 2, ... имеет место Л Ь-фпЛг|Л В вы-
г
воде цепочки фЛф из Л применяются правила, содержащие в правых частях вспомогательные символы; но длины правых частей таких правил больше единицы. Поэтому фф ф А. Поскольку грамматика Г приведенная, при Аф1 (/ — начальный символ) найдутся такие цепочки g и т], что / I— |Лг\. Кроме того, найдутся такие г
цепочки г, и, v, х, у в основном словаре, что A h г,
г
фН«, 'ФН v, gN*. лИу (Н означает «выводима г г г г г
в Г из или совпадает с»), причем uv ф А. Поэтому при любом п = 1, 2, ... из / будет выводима цепочка = = xunzvny (так при А ф /, при Л = / имеем вместо этого цепочку unzvn), и при щ ф п2 цепочки и различи^.
2) Если в грамматике нет циклических вспомогательных символов, то все деревья выводов просты, и их число, а тем более число выводимых из начального символа цепочек, конечно.
Теорема 4.2. Существует алгоритм, позволяющий по любой Ъ-грамматике Г распознать, является ли язык L(T) конечным.
Доказательство. В силу леммы 4.9 для выяснения вопроса о конечности языка L(V) достаточно перестроить Г в соответствии с леммами 4.1 и 4.8, а затем проверить все вспомогательные символы на цикличность (лемма 4.6).
