Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Теорема 5.6 (теорема Клини). Класс регулярных языков совпадает с классом непустых ОА-языков. Более того, по всякой ОА-грамматике Г, порождающей непустой язык, можно построить регулярную формулу *&, задающую /-(Г), а по всякой регулярной формуле 51 — ОА-грамматику Г, порождающую задаваемый этой формулой язык.
Доказательство, а) Поскольку ОА-грамматики для языков {ах}, ..., {ап}, {А} строятся тривиальным образом, построение нужной ОА-грамматики для заданной регулярной формулы обеспечивается теоремой 5.4.
б) Вторую половину теоремы докажем индукцией по числу s дуг диаграммы данной стандартной ОА-грам-матики Г. Если 5 = 0, язык Ь(Г) может быть непустым лишь тогда, когда он состоит из одной пустой цепочки, так что в этом случае имеем §1 = А. Пусть утверждение доказано для s — 1 и Г —стандартная грамматика
166 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
с диаграммой D из s дуг. Выбросим из D какую-либо дугу, идущую из начального узла / в узел В и помеченную символом а. Полученную так диаграмму обозначим через Du диаграмму, возникающую из D} при перенесении начального узла в В, — через D2, диаграмму, возникающую из D\ при перенесении заключительного узла в /,— через D3 и диаграмму, возникающую из Ь2 при перенесении заключительного узла в •
I, — через D4 (рис. 11). (На рис. 11 буквой К обозначен один из заключительных узлов диаграммы D, а цифрами 1, 2, 3, 4 в кружках — примеры путей в Du /?2, D3, Z)4 соответственно.) Грамматику с диаграммой Diy i = 1, 2, 3, 4, бу- : дем обозначать Г*.
В силу индуктивного предположения можно построить регулярные формулы Я{, i = 1, 2, 3, 4, задающие языки L(Ti).
Всякий полный путь в D, оче-Рис. 11. видно, либо является полным путем в Dj, либо представляется в виде lariiari2• • • где a— дуга (/,В), | — полный путь
в /?з, rii, • • •, цн — полные пути в D4 (k = 0, 1,...) и ? — полный путь в D2. Ясно также, что каждый путь, представимый в таком виде, является полным путем в D. Поэтому 1(Г) = L(Ti) UL(r3) (а1(Г4) )*aL(r2), так что L(r) задается регулярной формулой %1 U^з{а%1)*а^2-Следствие. Класс О А-языков есть замыкание класса конечных языков относительно объединения, умножения и итерации.
Замечание. Теорема 5.6, как ясно из ее доказательства, останется справедливой, если вместо произвольных ОА-грамматик рассматривать только такие, в диаграммах которых нет циклов (т. е. ОА-грамматики, порождающие конечные языки), а вместо произвольных регулярных выражений — многочлены.
Пример. Языки, порождаемые грамматиками, диаграммы которых показаны на рис. 8, задаются соответственно формулами ((a U b) (d\)bcb)*bce)* (AU (all U6) (d\}bcb)*b\e\)(\)c))x (aiO .s. Uan)*(aiO U«n), <fab*bt
? x
ОПЕРАЦИИ НАД ОА-ЯЗЫКАМИ
167
Дальнейшие примеры см. в упражнении 1.6.
В заключение докажем еще одну теорему, дающую очень удобный критерий автоматности языка.
Теорема 5.7. Для того чтобы язык L в словаре V был ОА-языком, необходимо и достаточно, чтобы существовала согласованная с ним конгруэнция конечного индекса на V*. (Определения конгруэнции и согласованности см. ниже, стр. 316 и 318.)
Доказательство, а) Пусть T={V,W,1,R)— стандартная ОА-грамматика и L(T) = L. Для каждой цепочки х ^ V* обозначим через О (х) множество всех пар (А, В), A, B^W, обладающих следующим свойством: в диаграмме Г существует путь из А в В, производящий х. Положим xRy, если 0{х)=0(у). Легко видеть, что R — конгруэнция. Индекс R не превосходит числа всевозможных подмножеств множества W2 и, следовательно, конечен. При этом ж е L тогда и только тогда, когда О(х) содержит пару вида (/, С), где С — заключительный узел диаграммы Г. Таким образом, принадлежность х к L вполне определяется множеством О(х), а это означает согласованность R с L.
б) Пусть R — согласованная с L конгруэнция конечного индекса на V*, А —произвольный R-класс и х е V*. Все цепочки вида гх, где геЛ, будут, очевидно, принадлежать одному и тому же У?-классу В; мы будем говорить, что х переводит А в В. Определим теперь ОА-грамматику Г = {V, W, I, R) следующим образом: W
есть множество всех У?-классов; I — класс, содержащий Л; R состоит из всевозможных правил вида А —*? аВ, где а — элемент V, переводящий А в В, и вида А—>-Л, где A s L. Ясно, что цепочка леР тогда и только тогда производится путем диаграммы Г, идущим из А в В, когда она переводит А в В. В частности, х производится полным путем, т. е. принадлежит L(T), тогда и только тогда, когда х переводит / в некоторый «заключительный» класс, а это, поскольку Ае/, равносильно тому, что х сама принадлежит «заключительному» классу; но объединение таких классов совпадает с L.
Из доказанной теоремы и леммы ПП. 1 (см. ниже, стр. 318) вытекает
•168 СПЁЦИАЛЬНЫЁ КЛАССЫ БЁСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
Следствие. Для того чтобы язык L в словаре V был ОА-языком, необходимо и достаточно, чтобы отношение ФФ имело конечный индекс.
V.L
Теорема 5.7 и сформулированное только что следствие часто оказываются полезными, когда надо доказать, что тот или иной язык не автоматный. Рассмотрим, например, язык L = {anbn\ri = 1,2,...}. Если бы отношение 4^ имело конечный индекс, то среди
