Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Замечание. Эту теорему нетрудно было бы доказать и чисто алгебраическим методом, построив систему уравнений, определяющую L, по системе, определяющей М.
§ 14.3. алгебраическое описание а-языков
Поскольку один и тот же А-язык может порождаться несколькими разными А-грамматиками или конечными автоматами, описание А-языка с помощью конкретной грамматики или конкретного автомата может обладать «случайными» особенностями, которые не являются «внутренне» присущими языку. Чтобы избавиться от подобных особенностей, целесообразно попытаться дать чисто алгебраическое описание А-языков, трактуя их как подмножества свободной полугруппы. Гл. XIV. Дополнительные сведения об автоматных языках 219
Из методических соображений мы начнем с рассмотрения некоторого конечного автомата, от которого в ходе рассуждений мы сможем затем избавиться.
14.3.1. Продолжение функции переходов
Рассмотрим следующий (детерминированный) конечный автомат:
. алфавит 91 = {а,- | 1 <«}; .. множество состояний 2 = {Sj I 0 </</?};
... начальное состояние So є E и множество заключительных состояний Effl с: 2;
.... функция переходов /, заданная множеством команд вида
IahSj) -+Sh.
Функция переходов определена на некотором подмножестве декартова произведения 91 X Е; ситуации, принадлежащие дополнению к этому подмножеству, не появляются в левых частях команд автомата, и в случае, если автомат оказывается в подобной ситуации, он останавливается. Присоединим к множеству состояний S состояние остановки $ и положим f (OitSj) = $ для любой пары (a,, Sj), не являющейся левой частью какой-либо команды. Теперь функция переходов определена на всем множестве 91 X E и принимает значения из 2 U {$}.
Продолжим далее эту функцию переходов / на множество 91* X E следующим образом (ср. п. 10.2.3): пусть X — цепочка из 91* и Sj — состояние автомата; тогда значением функции fg — продолженной функции переходов — для пары (X, Sj) будет состояние, в которое перейдет автомат после того, как, начав работать в состоянии Sj, он прочел (или пытался прочесть) слева направо цепочку X. Формальное определение fg выглядит так: если 1, т. е. X = ait то fg(M, S1) = f(Oi, Si)-, если fg определена для всех цепочек длины q и X = b і ... bqbq+i, є 91, то fg(X,Sj) =• = f(bq+ufg(b, ... bq, Si)), если /g(6, ... bq, Sj) Ф $, и UXtSi)= $, если fg(b 1... bq, Sj) = $.
Аналогичным образом можно определить функцию fd, соответствующую чтению цепочек справа налево.
Пример. Пусть имеется автомат- 91 = {a, b}\ E = {S0, Sb S2, S3); начальное состояние So; = {S2, S3); / задана таблицей
а Ь
s0 s1 $
s1 s1 s2
s2 sj s2
s3 sj $ 220
Часть III. Алгебраический подход
и допускает язык
{ambnaq 11 < m, 1 </г, 0 <</}.
Имеем
fgiabba, S0) = S3-, fg(abab, S0) = $; fg(abba, S1J = S3; fg(abbb, S1J = S2 и т. д.
14.3.2. Разбиение свободной полугруппы, определяемое конечным автоматом
Пусть имеется конечный автомат с алфавитом Я; пусть, далее, fg — функция переходов, соответствующая чтению цепочек множества Я* слева направо, и St- — состояние автомата. Рассмотрим отношение © на Я*, определенное следующим образом:
A®B&WSt)[fg{A, Si) = fg(B, Si)].
Ясно, что © есть отношение эквивалентности. Пусть А®В и С — произвольная цепочка из Я*. Тогда из равенств
fg(A, Si) = fg(B, S,) = Sfe
следует, что
fg(AC, Si) = fg(C, Sk) = fg(BC, Si).
Таким образом, отношение © совместимо с конкатенацией вправо.
Классам разбиения, индуцируемого отношением ©, взаимно однозначно соответствуют отображения SbSU {$} (2 — множество состояний автомата), получаемые при фиксировании А в fg(A,S). Поэтому число классов не превосходит числа всевозможных таких отображений, которое равно (п + 1)п, где п — мощность 2.
Следовательно, фактормножество Я*/® конечно; иначе говоря, индекс отношения © конечен ').
') Индексом отношения эквивалентности определенного на множестве M1 называется число классов эквивалентности, на которые 3? разбивает M1 — Прим ред. Гл. XIV. Дополнительные сведения об автоматных языках
221
Рассматриваемый автомат допускает цепочку X тогда и только тогда, когда ой может ее прочесть, начав чтение в начальном состоянии So и закончив в одном из заключительных состояний, иначе говоря, когда fg(X,S0) еї„, где Sico — множество заключительных состояний. Это означает, что допускаемый автоматом язык представляет собой объединение некоторых классов разбиения, индуцированного отношением О, а именно тех классов, для которых соответствующее отображение SbSU {$} принимает на So значения, принадлежащие S0,.
Аналогичным образом можно было бы рассуждать, заменив fg на fd-
Итак, имеет место
Предложение. Конечный автомат А с алфавитом Я определяет на свободной полугруппе 91* отношение О (соответственно имеющее конечный индекс, совместимое вправо (соответственно влево) с конкатенацией и такое, что язык, допускаемый автоматом А, есть объединение некоторых классов разбиения, индуцируемого отношением © (соответственно
Пример. Рассмотрим автомат, определенный в предыдущем пункте. Порождаемый им язык представляет собой объединение языка
