Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ ПП.2] ЗАМЕЩАЕМОСТЬ И ВЗАИМОЗАМЕЩАЕМОСТЬ
323
есть конфигурация 2-го ранга с результирующим с; действительно, из всех цепочек языка L только в def имеет» ся вхождение de, не перекрывающееся с вхождениями конфигураций 1-го ранга, и при этом cfeL Цепочка ef не является конфигурацией 2-го ранга с результирующим g, поскольку def не содержит вхождений конфигураций 1-го ранга, и все же gf^L. Аналогично устанавливается, что ff не есть конфигурация 2-го ранга с результирующим с. Следующий шаг будет состоять в проверке оставшихся цепочек ef и ff на «конфигурацион-ность 3-го ранга»; поступая, как выше, убеждаемся, что ef является конфигурацией 3-го ранга (с результирующим g), a ff — нет. Наконец, устанавливаем, что ff не является и конфигурацией 4-го ранга. Итак, имеем
Б (L) = {ge, cf, fff},
K(L) = {(bd, a) (aa, g), (abd, g), (bda, g), (bdbd, g),
{de, c), {ef, g)},
n{L) = {(bd, a), (aa, g), (de, c)(ef, g)}.
Пр им ер 2. Пусть L'={bncbn\n — 0, 1, ...}, L=a+L'a+. Легко видеть, что ®a(L) = 4Fa(L) = a+, ФЬ(Ц = {Ь}, Ф C(L) = XVC(L) = L'. Поэтому B(L) = {aca], K(L) = ={(ат, а)\т = 2, 3, ...} U{(*, с)\х е L'}, П(L) = {(aa, а), (ЬсЬ, с)}.
Дальнейшие примеры см. в упражнениях ПП. 2, 3,7; см. также ниже пример 3.
Теорема ПП. 2. Всякий конечно характеризуемый язык является бесконтекстным. При этом по заданным конечным E(L) и П(L) можно построить Б-грамматику, порождающую L.
Доказательство. Пусть L — конечно характеризуемый язык в словаре V. Сопоставим каждому а е V новый символ а и положим V = {а\а е V). Для каждой цепочки х = ах ... ak, где аь ..., asel/, k^l, будем полагать х — ах ... ak; если у=х, будем писать х—у. Введем еще один символ I фУ \}V и рассмотрим грамматику Г = <1/, FUW, /, U R.2 U Яз), где #,={/-» -+z\z <= B(L)}, R2 = {a-*x\(x, а)^П(1)}, R3 = {a^ -»a|ael/}. Покажем, что L(Y) = L.
I. Пусть w = L(T). Тогда найдется такой вывод (/ = соо, ..., сод, ..., о)„ = w) в Г, что на первом его
П*
324
ЗАМЕЩАЕМОСТЬ
[П. II
шаге применяется правило из Ri, на всех следующих шагах до k-ro включительно (1 < k ^ п — 1) — правила из Rt и на всех остальных шагах — правила из Rs-Поскольку Й1 efi(L) gL и для каждого i = 2, ..., k цепочка й, получается из i подстановкой некоторой конфигурации вместо ее результирующего, имеем ©б е L; но = w.
II. Чтобы показать, что is ЦГ), достаточно убедиться, что всякая цепочка w е ? выводима в Г из /. Но это легко сделать, применив индукцию по |ш| и воспользовавшись рассуждением, аналогичным примененному в доказательстве леммы ПП. 2.
Теорема ПП. 2 не может быть обращена. Более того, как показывает следующий пример, даже A-язык может не быть конечно характеризуемым.
Пример 3. Пусть L = {bab} U bcb+cb U (а+ (J cb+c)+‘ Ясно, что Фа(?) = {а} U cb+c, <P6(L) = {6}, Фс (?) = {<?} (например, в bcbcb первое вхождение Ь нельзя заменить ничем, а первое вхождение с можно заменить только цепочкой вида cbh, но такой цепочкой при 1 нельзя заменить второе вхождение с). Поэтому K{L) =
= {(cbmc,a) \т=\, 2, ...},откуда B(L) = {bab} U а+\ все конфигурации здёсь, очевидно, простые, так что П(Ь), как и B(L), бесконечно.
Один частный класс А-грамматик, приводящий к конечно характеризуемым языкам, указан в упражнении ПП. 4.
§ ПП.З. Окрестности, классы и типы
Рассмотренная в предыдущем параграфе система по- ? нятий может служить примером анализирующей лингвистической модели. Эта модель описывает некоторые отношения, возникающие между элементами языка в речи (более конкретно — в предложении), или, как говорят лингвисты, «синтагматические отношения»; модели, описывающие такие отношения, принято также называть синтагматическими в отличие от парадигматических моделей, описывающих отношения между элементами языка в его системе — «парадигматические отношения». В настоящем параграфе будет
« ПП.З]
ОКРЕСТНОСТИ, КЛАССЫ И ТИПЫ
325
рассмотрена одна из анализирующих моделей этого последнего типа, также основанная на понятии замещае-мости.
Пусть L — язык в словаре V, р — отношение эквивалентности на М и 0 — алфавитный гомоморфизм V* на (V/p) *- Пусть, кроме того, р'—некоторое укрупнение р. Мы будем говорить, что р' есть L-р егулярное укрупнение р, если любые два p-класса, содержащиеся в одном р'-классе, взаимозамещаемы относительно 0(L). В частности, мы получим L-регулярное укрупнение р, если будем считать два элемента V эквивалентными тогда и только тогда, когда они содержатся в p-классах, взаимозамещаемых относительно Q(L). Такую эквивалентность мы будем называть L-n р о и з в о д н о й для р; она является, очевидно, наибольшим /.-регулярным укрупнением р, т. е. служит укрупнением любого L-регулярного укрупнения р.
В дальнейших утверждениях L будет означать язык в словаре V, pi и рг — эквивалентности на V такие, что р2 — укрупнение pi, и 01, 02, r)i2 — алфавитные гомоморфизмы V* на (F/pi)*, V* на (F/рг)* и (K/pi)* на (У/рг)* соответственно.
Лемма ПП.З. Если р2 — L-регулярное укрупнение pi, то Xe0i(L) тогда и только тогда, когда 1112(Х) (= е 02(Ь).
Доказательство. а) Поскольку 02(L) = = tii2(0i(?)), из Xe0i(L) вытекает rii2(X) <= Q2(L).
