Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
§ 10.8. ОДНОСТОРОННИЕ КОНЕЧНЫЕ ПРЕОБРАЗОВАТЕЛИ
10.6Л. Автомат типа X
Пусть 91 — конечный автомат; снабдим его выходной лентой, на которой он будет писать после каждого такта работы некоторый символ из выходного алфавита Vs= {?>;}. У нас получится автомат нового типа принадлежащий к классу односторонних конечных преобразователей. Команды автомата ї имеют вид
(ah S,)-+[Sk, bi);
когда преобразователь ? посредством конечного автомата 91, входящего в его состав, определяет допустимость некоторой предъявленной цепочки /, он одновременно дает «перевод», или транскрипцию, этой цепочки в {?>{}*. Транскрипция цепочки f, полученная преобразователем — транскрипция f относительно — обозначается через ї(/).
Автомат ? можно изобразить с помощью диаграммы (графа), вершины которой соответствуют его состояниям. Команде (ai, Sj)-*
(Sh, bi) отвечает в этой диаграмме дуга, помеченная парой (ai,b[) и ведущая из Sj в Sh- Легко видеть, что множество транскрипций цепочек, допускаемых преобразователем ?, есть А-язык.
Если в командах преобразователя J поменять ролями а* и Ьи т. е. перейти к командам вида
(bh Sj)-+(Sk, at),
') Можно доказать, что любая КС-грамматика, порождающая неавтоматный язык, имеет самовставление. — Прим. ред.
2) Здесь используется то обстоятельство, что, в силу п. 10.4 2, язык тогда и только тогда является А-языком, когда таковым является его дополнение. — Прим. ред. Гл. X. Автоматные языки и конечные автоматы
173
мы получим преобразователь обратный к Обратный преобразователь изображается диаграммой, которую легко построить по предыдущей, пометив дуги парами (Ь,а) вместо (а,Ъ).
10.6.2. Формальное определение
В наиболее общем виде односторонний конечный преобразователь SE определяется заданием следующих объектов:
1) входной алфавит Ve = {«і, ...} и выходной алфавит Vs = = {?>ь ...}, каждый из которых содержит по меньшей мере две буквы;
2) конечное множество состояний E = (S0, ...};
3) отображение, определяющее переход в новое состояние (функция переходов):
4) выходное отображение:
Преобразователь, приведенный в начальное состояние S0, читает самый левый символ цепочки f = а^а^ ... а1п; затем он переходит в новое состояние, отвечающее паре (S0, аг1), и пишет на выходной ленте символ (или цепочку), отвечающий этой же паре. Затем он читает очередной символ цепочки /, т. е. аІ2, и т. д.
Описанные преобразователи называются односторонними потому, что транскрипция выполняется в ходе чтения предъявленной цепочки строго в одном направлении — слева направо.
Если преобразователь оказывается в ситуации, для которой его программа не содержит соответствующей команды, он останавливается. Если же он доходит до конца читаемой цепочки, то одновременно он заканчивает и ее транскрипцию.
10.6.3. Транскрипция КС- языка
Рассмотрим теперь КС-грамматику G и односторонний конечный преобразователь SE. Спрашивается, к какому классу принадлежит язык Z(L), представляющий собой транскрипцию языка L = = L(G) (точнее, пересечения L(G) с языком, который будет допускать преобразователь SE, если лишить его выхода) относительно SE.
Можно показать, что SE (L) есть КС-язык; мы построим для него КС-грамматику G'.
Пусть Va = (At- I O^t — вспомогательный словарь грамматики G, где A0 — аксиома; Vt = {afi; {S^}—множество состояний преобразователя Т\ S0 — его начальное состояние, a {S/} — его заключительные состояния.
Правила грамматики G' определяются следующим образом.
Аксиомой в G' является новый символ Aq, прочие нетерминальные символы — это тройки вида (Si, a, Si), где Si и Sj суть 174
Часть II. Некоторые замечательные классы языков
состояния преобразователя а а — символ (терминальный или вспомогательный), используемый грамматикой G. Кроме того,
1) для всякого заключительного состояния Sf грамматики G выражение Лд—>(.S0, Л0, Sf) есть правило грамматики G';
2) если Am-*-ai... ан есть правило грамматики G, то для любых і, /, ?i, ..., ?ft_i грамматика G' содержит правило
(Si, Am, Sj) —>(Si, си, S?,)(S?,, -?) ••• (?-,' °А» sI)'
3) если (aj, Sp)-*(Sq, bi) — команда преобразователя Т, то G' содержит правило
(Sp, ah Sq) ->6г.
Нетрудно показать, что L(Gr) = % (L).
Для частного случая, когда преобразователь просто копирует входную цепочку, т. е. когда его команды имеют вид (OitSj)-* -+(Sh, щ), из доказанного утверждения получается следующая
Теорема. Пересечение КС-языка и А-языка есть КС-язык, Глава XI
ЗАДАНИЕ ЯЗЫКОВ С ПОМОЩЬЮ СИСТЕМ УРАВНЕНИЙ
§ 11.1. ФУНКЦИИ, АРГУМЕНТАМИ И ЗНАЧЕНИЯМИ КОТОРЫХ являются ЯЗЫКИ
11.1.0. Операции
Выше мы определили ряд операций над языками, из которых здесь нам понадобятся две:
. теоретико-множественное объединение L U М\ эта операция коммутативна и ассоциативна; .. умножение LM, которое заключается в образовании декартова произведения двух языков с последующей конкатенацией членов каждой пары:
LM = {ху I X є L, у <= М}.
Умножение языков ассоциативно, но не коммутативно, как и операция конкатенации цепочек, к которой оно восходит.
