Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Первое уравнение имеет вид
S = Aa1^a,+ ... + ClaAal + flY[ + ... +Ayft!
оно гарантирует нам, что цепочки языка Ks будут начинаться с допустимых букв и что Ks будет содержать все однобуквенные цепочки из / П /.
Остальные п уравнений построены по следующей общей схеме:
/ п
Ax = Ii O(^lPll)Ae11+2 б (Л, ц) «vV Я = 1.....п.
U=I ^ H=I
Здесь вторая сумма задает все буквы aприсоединимые к а% конкатенацией справа, но не являющиеся концевыми в цепочке; первая сумма задает те из допустимых заключительных букв, которые могут присоединяться к ах конкатенацией справа.
Эта система уравнений порождает язык Ks (и вспомогательные языки, выводимые из Au ..., An как из аксиом) и притом однозначно. Выписанная система соответствует, очевидно, правосторонней А-грамматике; это дает еще одно доказательство автоматности языка Ks-
Пример. Возьмем язык Ks, рассматривавшийся в примере на стр. 214. Его терминальный алфавит состоит из пяти букв: а, Ь, с, d, f\ нетерминальный алфавит будет включать шесть букв: аксиому S и пять вспомогательных символов А, В, С, D, F.
Соответствующая система уравнений может быть записана ч виде матрицы, имеющей 6 строк (по числу уравнений) и 7 столбцов: пять для одночленов типа аА, ЬВ, ... и два — для заключительных букв си/. Вот эта матрица:
Допустимые начала Допустимые концы -> <-->
S = аА + ЬВ + сС + с
A = сС + dD + с
B = ьв + сС + ;f + c + f
C = dD
F = cC + fF + dD + c + f
D = аА + ЬВ + сС + fF + c + f Гл. XIV. Дополнительные сведения об автоматных языках
217
Из такой записи системы уравнений можно непосредственно «вычитать» множество допустимых начал, множество допустимых концов и матрицу переходов, т. е. матрицу разрешенных диграмм (клетки, взятые в полужирную рамку).
14.1.3. Упражнения
1. Исследовать стандартный А-язык, определяемый четверкой (VT, /, J, А), где
Vr = {а, Ь, с}, l = {a,b}, J = {с}, A = {bc, са, cb, ее).
Написать соответствующую систему уравнений и решить ее; дать простую характеристику языка.
2. Указать достаточные условия того, чтобы четверка (VT,I, J, А) определяла пустой язык, например:
а) «плохой выбор» множества I (построить пример);
б) «плохой выбор» множества J (построить пример).
§ 14.2. свойства стандартных а-языков
14.2.1. Теорема
Итак, всякий стандартный А-язык порождается системой «пра-волинейных» уравнений, определенной над терминальным алфавитом Vt = fan I 1 ц п} и вспомогательным алфавитом Va = = I 0 Ж п} и удовлетворяющей следующим двум условиям (KS):
. нетерминальный символ A0 (аксиома языка) встречается только в одном уравнении, и притом в его левой части; .. все члены правых частей уравнений имеют вид a?A? или a?.
Обратно, рассмотрим такую систему уравнений. Если записать ее в виде матрицы, рассмотренной в предыдущем пункте, то мы сможем сразу усмотреть в ней множество допустимых начал, множество допустимых концов и матрицу допустимых диграмм: это значит, что наша система задает стандартный А-язык.
Теорема. Для того чтобы язык был стандартным А-языком, необходимо и достаточно, чтобы его можно было задать системой уравнений, удовлетворяющей условиям (KS).
14.2.2. Стандартные А-языки и автоматы
Легко показать (мы предоставляем это читателю), что конечный автомат, сопоставляемый стандартному А-языку посредством системы уравнений типа (KS), является детерминированным автоматом.
Поскольку при этом запрещенные переходы задаются списком запрещенных диграмм, то для проверки допустимости предъявленной цепочки достаточно хранить в памяти автомата одну букву. 218
Часть III. Алгебраический подход
Тем самым автомат оказывается 1-определенным (см. п. 10.3.3); таким образом, стандартный А-язык является 1 -определенным.
14.2.3. Отображения стандартных А-языков на произвольные А-языки
Стандартные А-языки интересны не только в силу своей особой простоты, но еще и потому, что с их помощью можно дать простое описание структуры произвольного А-языка. В самом деле, имеет место следующее утверждение.
Теорема. Для всякого А-языка M существуют стандартный А-язык L и гомоморфизм ср, такие, что ф(L) = М.
Доказательство. Пусть язык M порождается А-грамма-тикой G с терминальным алфавитом Vt- Возьмем в качестве нового терминального алфавита Vt множество всевозможных пар вида (а, А), где а є Vt и А — вершина графа грамматики, и определим стандартный А-язык L в алфавите Vt следующим образом:
— допустимыми началами будут пары (а, А), такие, что в графе G имеется дуга, ведущая из начальной вершины в Л и помеченная символом а;
— допустимыми концами будут пары (Ь,В), такие, что ? — заключительная вершина и b — пометка на некоторой дуге, ведущей в Ь;
— разрешенными диграммами будут пары ((аь Ai),(а2, A2)), такие, что: (а) Oi— пометка на некоторой дуге, ведущей в Ai; (б) имеется дуга, ведущая из Лі в A2 и помеченная символом а2.
Попросту говоря, L будет состоять из всех «полных путей» в графе грамматики G.
Гомоморфизм ф, определенный условием ф(а, А) = а, будет, очевидно, отображать L на М.
