Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Если Д с У* есть А-язык, то множество цепочек, образы которых принадлежат Д, также является А-языком.
Это доказывается путем рассмотрения следующей эквивалентности: / ~д/' тогда и только тогда, когда класс эквивалентности г] (S, f) по допустимым концам относительно Д совпадает с классом эквивалентности цепочки /'.
14.4.5. Еще о языке rj (S,X*)
Мы видели, что т] (S, X*) есть А-язык. Можно поставить следующий вопрос: если дан алфавит Y и А-язык LczY*, то всегда ли Гл. XIV. Дополнительные сведения об автоматных языках
229
можно построить такое преобразование, чтобы т)(5, А*) совпало с L?
Ответ на этот вопрос оказывается отрицательным. Пусть, например, Y = {а, Ь}\ нетрудно убедиться, что не существует преобразования, которое отображало бы X* на а*Ь (чтобы построить такое преобразование, пришлось бы отказаться от детерминированности).
14.4.6. Произведение односторонних преобразований
Определим правое одностороннее перобразование так же, как мы определяли левое одностороннее преобразование; для этого достаточно изменить направление чтения. Отображение, задающее функцию переходов для правого преобразования, мы будем записывать следующим образом:
(tr'): X X Sr -*?. 2'.
Отображение (tr') ставит в соответствие паре (х, S') состояние, которое мы будем обозначать через xS'.
Теперь можно рассматривать композицию односторонних преобразований, как левых, так и правых: первое отображает X* в Y*, второе— Y* в Z* и т. д. Результат композиции преобразований называется их произведением.
Имеет место следующий результат: если X и Z — произвольные алфавиты и LcZ* есть А-язык, то существуют такое левое преобразование и такое правое преобразование, что их произведение отображает X* на L.
Данное утверждение доказывается сначала для стандартного А-языка IZ* П Z*J \ Z*VZ* (напомним, что / — множество начальных букв, I — множество заключительных букв, V — множество запрещенных диграмм). Затем следует перейти к общему случаю с помощью гомоморфизма, описанного в п. 14.2.3.
14.4.7. Двусторонние преобразования
Чтобы определить двустороннее преобразование множества X* в множество К*, нужно задать две функции переходов для двух множеств состояний:
(tr):
{S, х) —>• Sxi (tr'): IXS'-^S', (х, S')-+xS'.
Кроме того, должно быть задано следующее отображение: T1: (2, X1 2') —*¦ Y,
(5, X, S')-+4(S, X, S'). 230
Часть III. Алгебраический подход
Цепочка Ijil ... уіг будет по определению образом цепочки Xil... Xir при двустороннем преобразовании, исходящем из состояний 5 и 5' [Xii.....Xir <= X, уіх, ..., Уіг є Y, S&2, S'<=
є 2'), если найдутся такие последовательности состояний S0, ... -,SfGS1S;.....Sfr є Sf, что
а) S0 = S, Si = S0Xfi, ..., Sr = S,._iX;r;
б) Sr = S , Sr-i = XirSr, ..., So = XifSі;
в) Уи = tI(So, Xi1, SD, г/і: =Tl(S), xh, S'2).....yir = r\{Sr_x, xir> S;).
14.4.8. Двусторонние преобразования и А-языки
Результаты, полученные для случая одностороннего преобразования, можно обобщить и на случай двустороннего преобразования: если Г есть А-язык, то и T](S, Г, S') есть А-язык; если Acz Y* есть А-язык, то и t]-1(S, A, S') — также А-язык.
Для доказательства этих утверждений полезно представить преобразование с помощью графа, вершинами которого служат пары
(S1S'), а из (S1-, Sa) в (Sq, Sy) идет дуга, помеченная парой
(Xj,уt), тогда и только тогда, когда Sa = SiX/, S'= x/Sy, yt =
= ri (Si, Xh Sy).
14.4.9. Упражнения
1. Преобразование, переводящее X* в заданный стандартный А-язык.
Построим сначала левое одностороннее преобразование, отображающее X* в (XU{w})*, где а» — некоторый специальный символ. Каждому Xi є X будет отвечать состояние [х,]; кроме того, будут еще два состояния Si и S2.
Правила перехода из одного состояния в другое таковы:
S1X = [х] для ле/
SiX = S2 для X ф: I
[х,]х2 = [х2] ДЛЯ XiX2^F
[x,]x2 = S2 для ХіХ2є V.
Отображение ц определяется следующим образом:
Г] (Sj, х) = е для ЇЄІ T|(Si, х) = X для хфі Л (S2, х) = е л ([JCt], */) = <•> для X1X1S=V Л ([*,]> Xj) = X, для XiXjgiV. Гл. XIV. Дополнительные сведения об автоматных языках
231
Полученный таким образом язык следует перевести в заданный стандартный язык с помощью правого одностороннего преобразования (при построении которого должно быть учтено /).
2. Пусть т] — левое одностороннее преобразование множества X* в У* и ц — правое одностороннее преобразование У* в Z*.
Всегда ли существуют правое одностороннее преобразование ц' и левое одностороннее преобразование т]', такие, что
Пи = ц'ц'? Глава XV
ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О КС-ЯЗЫКАХ
§ 15.1. языки дика
15.1.1. Свободная группа
Пусть її = {a, b, .. } и її' = {а', b', ...} — два конечных непересекающихся алфавита с одинаковым количеством букв. Пусть между этими алфавитами установлено взаимно однозначное соответствие: а — a', b — Ь' ит. д. Пусть, кроме того, 33 = її U її'.
Обозначив через E пустое слово, зададим следующую систему 9Ї соотношений Туэ:
SR: аа' ~ а'а ~ Е, bb' ~ Ь'Ь ~ Е, ....
