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

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

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


Da содержит, помимо цепочки аа', все цепочки, имеющие вид

afi... fma',

где fi <= Dxp Xi Ф й, и только такие цепочки.

Чтобы выразить этот факт, воспользуемся уравнением

Da = аАа' + аа', (Ia)

где А — еще один нетерминальный символ, соответствующий некоторому языку. Этот язык содержит, в частности, Da', Db, Dy; точнее, он состоит из конкатенаций любых цепочек, принадлежащих Da' U Db U Db'. Следовательно, мы можем написать уравнение

А = (Da' + Db + Db') (А + Е), (2а)

где E — пустая цепочка

Что касается языка Дика D, то он соответствует уравнению

D" = (Da + Da' + Db + Dy) D' + Е. (3)

Уравнения типов (1) и (2) вместе с уравнением (3) задают некоторую грамматику языка Дика. Эта грамматика однозначна, поскольку она порождает слева направо Д-простые сомножители Цепочки, принадлежащей D*. 238

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

Пример. Возьмем цепочку abbaa'b'cc'bb'b'a', уже фигурировавшую в п. 15.1.5. В построенной нами грамматике эта цепочка имеет только один вывод '):

D4

15.1.9. Однозначная грамматика, порождающая ограниченный язык Дика

При построении грамматики для ограниченного языка Дика достаточно рассмотреть множества Da, Db и т. д., исключив Da',

Dy.....Теперь А, В, ... можно не различать, поскольку цепочки,

начинающиеся штрихованными буквами, не рассматриваются. В результате мы имеем

Da = aUa' + аа', Db = bUb' + bb', U = (Da + Db)(U+E), Dl = (Da + Db) Dr + Е. Аксиомой является D'r («ограниченный язык Дика»),

') Для простоты в дереве вывода не показаны пути, оканчивающиеся в Ь (кроме одного); эти пути не изменяют терминальную цепочку. — Прим. ред. Г л XV. Дополнительные сведения о КС-языках

239

Пример. Сюда подходит предыдущий пример, в котором сознательно была взята цепочка из Dr; надо только заменить А я В на U.

15.1-Ю. Упражнения

1. Пусть имеется алфавит X (содержащий как «нештрихован-ные», так и «штрихованные» буквы). Обозначим через f цепочку, которая получается из f обращением этой последней с последующим инвертированием штриховки. Положим

V = [V є= U I V ф U XX'}.

Иначе говоря, V состоит из цепочек языка U, никакие собственные начала которых не принадлежат U.

Доказать, что всякая цепочка ff є U единственным образом представляется как конкатенация цепочек из V.

2. Определение свободной группы. Пусть 91 = {a, a', b, b',...} — алфавит, состоящий из 2п «спаренных» букв (как все алфавиты языков Дика; ср. п. 1.3.2). Пусть, далее, имеются соотношения Туэ: аа' = a'a = E и т. д.

Для того чтобы слово в алфавите 91 было несократимо, необходимо и достаточно, чтобы ни одно вхождение буквы Xi не было смежным с вхождением «парной» буквы Xri.

Рассмотрим множество несократимых слов, включив в него пустое слово Е. Снабдим это множество операцией, которую мы будем обозначать точкой и называть умножением, следующим образом.

Чтобы получить произведение X -Y, нужно

Г. образовать конкатенацию XY;

2°. рассмотреть пару вхождений букв на стыке X и У;

— если эти буквы не «спаренные», то X- Y = XY;

— если они «спаренные», нужно вычеркнуть данную пару вхождений;

—• затем нужно проделать то же самое с буквами «на стыке» слов, оставшихся от X и У, и т. д. Кроме того, полагаем X-E = = E-X = X.

Примеры.

X — aba'cb, Y = с', X ¦ Y = aba'cbc';

X = aba', Y = ab', X-Y = a;

X = bac', Y = ca'b', X-Y=E.

Доказать, что множество несократимых слов, снабженное таким умножением, образует группу. 240

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

Поскольку не очевидна лишь ассоциативность, наметим путь ее доказательства.

Пусть X, Y, Z — несократимые слова; докажем равенство

(X-Y)-Z = X-(Y-Z).

Если хотя бы одно из слов X, У, Z пусто, то равенство очевидно. Поэтому можно сначала доказать его для случая, когда У — однобуквенное слово, а затем воспользоваться индукцией по длине У: допустим, что для |У| = т—1 равенство доказано; возьмем Y=Yiy, где I У, I =m — 1 и ye= «; имеем X -(Y • Z) =X - [(Yi • у) - Z] = =X-[Yr(yZ)] ит. д.

§ 15.2. стандартные кс-языки

15.2.1. Определение

Стандартным КС-языком Cs называется язык, представляющий собой пересечение языка Дика D* и стандартного А-языка Q:

Cs = DtOQ.

В п. 10.6.3 было показано, что пересечение КС-языка и А-языка является КС-языком; этот факт оправдывает только что сформулированное определение. Там же была указана процедура, позволяющая построить для указанного пересечения КС-грамматику. Эта грамматика будет однозначной, если таковы грамматики исходных языков D* и Q-

Примеры. Пусть имеется алфавит Я = {а, Ь, а', ft'}; Q определяется начальными буквами {a, b} и запретом диграмм вида х'у (т. е. переходов от буквы со штрихом к букве без штриха).

Пересечение языка Q с языком Дика в алфавите Я имеет вид

Cs = {/ff f є {а, ЬУ), где j означает то же, что в упр. 1 из п. 15.1.10.

15.2.2. Особенности цепочек, принадлежащих стандартным КС-языкам

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

Те особенности, которые восходят к стандартным А-языкам, сугубо локальны. Для проверки их выполнения достаточно линейно ограниченного конечного автомата: ему придется хранить в памяти ровно одну букву (прочитанную последней).
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed