Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
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. Особенности цепочек, принадлежащих стандартным КС-языкам
Цепочки стандартных КС-языков обладают особенностями двух типов, существенно различными по своей природе.
Те особенности, которые восходят к стандартным А-языкам, сугубо локальны. Для проверки их выполнения достаточно линейно ограниченного конечного автомата: ему придется хранить в памяти ровно одну букву (прочитанную последней).