Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 82

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 101 >> Следующая


Особенности, восходящие к языкам Дика, должны соблюдаться, так сказать, на неограниченном расстоянии. Для их проверки требуется автомат с неограниченной памятью. Правда, эти особенности касаются «неперекрещивающихся» пар вхождений символов, они отражают скобочную структуру языков Дика. Г л XV. Дополнительные сведения о КС-языках

241

Итак, мы видим, что стандартные КС-языки имеют достаточно простую и интуитивно ясную структуру. Уже это делает их интересными; однако значение этих языков определяется в основном следующей теоремой.

15.2.3. Основная теорема о КС-языках

Всякому КС-языку L можно сопоставить язык Дика D* (и даже ограниченный язык Дика Dr), стандартный А-язык Q и гомоморфизм ф, такие, что

? = ф(?>*П<2) (соответственно ? = ф(0*П<2)).

Иначе говоря, всякий КС-язык может быть получен посредством гомоморфного отображения некоторого надлежащим образом выбранного стандартного КС-языка.

Пример. Язык {ff} в алфавите {а, Ь} получается из стандартного КС-языка {/f}, рассматривавшегося в предыдущем примере, посредством гомоморфизма

а-* а

ф:

а -+а b-+b Ь'-+Ь

Для доказательства этой теоремы нам нужно ввести понятие простой грамматики и доказать два вспомогательных предложения.

Определение. Назовем КС-грамматику простой, если все ее нетерминальные правила имеют вид

h = 2 dt, і + S і, kbi, і, klfii, і, kct, i, klkCi, l, kat, /, ki і /, k

здесь латинские буквы обозначают разные (№!) терминальные символы, а греческие — нетерминальные символы.

Предложение 1. Для всякой грамматики G, порождающей язык L1 существует простая грамматика G' и гомоморфизм ф, такие, что L = ф(L(G')).

Дадим набросок доказательства. Если в G имеется правило вида

I ,-+UlfVlffWl'",

где и, V и W — терминальные цепочки, то вводится нетерминальный символ ? и правила

Ii^Zwlffft l->ulfu I". 242

Часть III. Алгебраический подход

Если в G имеется правило

то вводится нетерминальный символ г] и правила

h и?Ч

Т]-> V.

Таким образом мы добьемся, чтобы все правила, содержащие в правых частях нетерминальные символы, имели вид

?, -* ulvl'w.

Для каждой тройки {и, v, w) введем новые символы а, Ъ, с и определим гомоморфизм ф так, чтобы

Ф (а) = и, ф(а) = е,

Ф(6) = е, ч»(5) = о,

ф (с) = е, ф (с) = W

(е — пустая цепочка). Затем мы можем включить в Gf правила

li-^abl5clfca\

гомоморфизм ф превратит их в правила грамматики G, и мы будем иметь L = ф(1')-

Теперь мы можем приступить к доказательству основной теоремы.

Пусть G есть КС-грамматика, порождающая язык L; построим сначала простую грамматику Gf в соответствии с предложением 1. Грамматике G' мы сопоставим стандартный А-язык R и язык Дика D*.

, В языке R разрешены диграммы следующего вида:

al, l.kbt, l,k> /, kdj, I, b[, j, fto/, і, m't

cI, I, kdk, h cU и kak, I, ml

a/,l,mt>l,/,kl ^hJtkCltmtl;

t>i,l,kci,i,kl Cui,kai,uhl di і'Ві і, m\ di_i'Siitnfi.

Здесь Of, і, ft, bi, jt ft, cit ft — буквы, a dit следует понимать как дву-буквенную цепочку 8itib{l і (при этом некоторые диграммы превращаются в триграммы, но разрешение таких триграмм легко свести к разрешению диграмм). .. D* есть язык Дика в алфавите X U Xf, где

X = {aitj,k, bhj,k, Chitk, oh[}. Г л XV. Дополнительные сведения о КС-языках

243

Основная теорема оказывается теперь непосредственным следствием следующего предложения:

Предложение 2. Пусть имеется простая грамматика G с правилами вида

It = 2 dit і + 2 di, j, tfii, і, kli&u і, kci, і, klk^i, і, h<*i, j, k>

l i, к

пусть имеются, далее, язык Дика D* и А-язык R, сопоставленные указанным выше способом грамматике G. Тогда для каждого і язык Lh состоящий из цепочек, выводимых в G из удовлетворяет следующему уравнению:

Lfl = D пяп(1К/.***1К/]-

I /, k I )

Доказательство удобно провести в два этапа; наметим их. Первый этап. Рассмотрим сначала грамматику

I = d + abl6c%ca,

полученную из G путем отбрасывания индексов и сохранения лишь одного нетерминального символа. Докажем предложение 2 для этого частного случая. А-язык R можно представить посредством следующей диаграммы:

b d с

L' состоит из d (т. е. бб) и некоторого множества Д-простых цепочек, начинающихся буквой а и удовлетворяющих ограничениям на сочетаемость букв, задающим язык R.

Пусть L" = D* П R П {аХ* U d!}. Требуется доказать, что L' = L".

Включение L' с: L" очевидно. Обратное включение докажем по индукции, воспользовавшись тем, что L" состоит из d и Д-простых цепочек вида abAibcA2a, где Л і и A2 суть Д-простые цепочки такого же вида (быть может, равные d). Доказательство того, что каждая такая цепочка принадлежит L', будет проводиться индукцией по «сложности» цепочки (начиная с d). При этом используется тот факт (п. 15.1.7), что всякая Д-простая цепочка имеет единственное представление вида afі ... fma, где Z1 є DX{.

Второй этап. Можно убедиться, что предыдущее доказательство сохраняет силу и для случая, когда буквы а, Ь, с, d имеют индексы. 244

Часть III. Алгебраический подход

15.2.4. Следствия из основной теоремы
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed