Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Часть III. Алгебраический подход
Таким образом, любой контекст, допустимый для А, допустим и для В, что и требовалось доказать.
13.2.3. Эквивалентность по допустимым концам
Если ограничиться контекстами, в которые левый (соответственно правый) член есть пустая цепочка, то из отношения =L мы получим другое отношение — эквивалентность по допустимым концам (соответственно началам).
Поскольку это понятие важно для нас, мы рассмотрим его независимо от взаимозамещаемости.
Пусть L — язык, содержащийся в свободной полугруппе Я*, а M и X — цепочки, принадлежащие Я*. Если MX <= L, мы будем называть X допустимым концом для M относительно L.
Пример. Я = {а, Ь, с}, L — «зеркальный язык»: L = {AcA\A е{а, 6}*}.
Тогда
для aabc существует ровно один допустимый конец, а именно Ьаа\
для aab допустимым концом является любая цепочка вида XcXbaa-,
для aabcbaa существует ровно один допустимый конец — пустая цепочка;
для aabcbb ни одна цепочка не является допустимым концом (множество допустимых концов для этой цепочки пусто).
Если пустая цепочка E является допустимым концом для А, то множество допустимых концов для А не пусто.
Определим теперь на множестве 91* отношение следующим образом: A%LB тогда и только тогда, когда А и В имеют одни н те же допустимые концы относительно L.
Это отношение, являющееся, разумеется, эквивалентностью, имеет место между А и В в следующих двух случаях:
1) либо ни А, ни В не имеют допустимых концов;
2) либо и для А, и для В существуют допустимые концы, причем всякая цепочка, являющаяся допустимым концом для А, является допустимым концом для В, и обратно.
Пусть A^lB и С е Я* — произвольная цепочка, рассмотрим цепочки AC и ВС.
Если множество допустимых концов для А и аналогичное множество для В пусты, то множества допустимых концов для AC и ВС также пусты.
Если X — допустимый конец для АС, то ACX^L и, следовательно, CX — допустимый конец для А; тогда CX — допустимый конец и для В. Поэтому BCX^L, откуда следует, что X — допустимый конец и для ВС. Г л. XIII. Г омоморфизм полугрупп
211
Следовательно, отношение Jl совместимо вправо с конкатенацией.
Рассматривая допустимые начала цепочек, можно ввести аналогичное отношение Zl, совместимое с конкатенацией влево.
Нетрудно видеть, что L есть объединение некоторых классов по отношению Sl- В самом деле, из ЛІ є L следует, что множество допустимых концов для M содержит пустую цепочку Е. Следовательно, для всякой цепочки Р, находящейся с M в отношении cSl, пустая цепочка E также является допустимым концом, откуда PE^L, т. е. P^L. Таким образом, если L содержит некоторую цепочку, то L содержит весь класс, в который входит эта цепочка.
Все сказанное можно сформулировать в виде следующего предложения.
Предложение. Язык Lcz 21* определяет в 21* отношеныг эквивалентности Sl по допустимым концам (соответственно отношение эквивалентности Zl по допустимым началам), совместимое вправо (соответственно влево) с конкатенацией.
Сам язык L есть объединение некоторых классов эквивалентности по Sl (соответственно по Sl)-
13.2.4. Свойства отношения St
Отношение Sl обладает следующими двумя свойствами:
1. Оно совместимо вправо с конкатенацией.
2. L является объединением классов эквивалентности по этому отношению.
Нетрудно видеть, что всякое отношение SR, обладающее этими двумя свойствами, либо тоньше, чем Sl, либо совпадает с ним.
Действительно, пусть SR — такое отношение; покажем, что из ASR? следует AiuB. В самом деле,
[АШВ & AC є L] [АСШВС & ACe=L]
(в силу совместимостиSR с конкатенацией вправо); но [ Астс & AC є= I] ВС єі,
так как L, будучи объединением классов эквивалентности, содержит ВС, если только L содержит АС.
Таким образом, всякий допустимый конец для А допустим и Для любого В, такого, что АШВ, и обратно, что и требовалось доказать.
Итак, доказана
Теорема. Отношение эквивалентности по допустимым концам относительно языка L является не более тонким, чем любое отношение эквивалентности, совместимое вправо с конкатенацией и такое, что L есть объединение классов по этому отношению. 212
Часть III. Алгебраический подход
§ 13.3. понятия, связанные с кодами
13.3.1. Определение кода
Пусть Xn Y — конечные алфавиты, состоящие не менее чем из двух букв каждый; тогда всякий мономорфизм множества Y* в X* называется кодированием.
Как всякий гомоморфизм, мономорфизм определяется образами образующих полугруппы У*, т. е. образами букв алфавита У. Множество образов букв алфавита У называется кодом-, кодирование становится возможным благодаря наличию кода.
Пример. Пусть У = {х, у, z, t), X = {0, 1}; в качестве образов б>кв X, у, z, t возьмем соответственно 00, 01, 10, 11. Ясно, что мы определили мономорфизм У* в X*. Если цепочка из X* является образом некоторой цепочки из У*, то она является образом только этой цепочки.
Например:
1101010100 расшифровывается как t у у у х.
Задавая образы букв алфавита У случайным образом, мы получим гомоморфизм, который не обязательно будет мономорфизмом.
