Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Алгебраические свойства КС-языков

Алгебраические свойства КС-языков


В этой лекции мы рассмотрим некоторые операции над КС-языками, относительно которых множество всех КС-языков замкнуто. Напомним, что множество всех регулярных языков (в произвольно фиксированном алфавите) замкнуто относительно операций (конечного) объединения, соединения, пересечения, дополнения (до универсального языка) и итерации. В этом разделе мы докажем прежде всего что множество КС-языков замкнуто относительно операций объединения, соединения и итерации. Потом мы увидим, что пересечение двух КС-языков, вообще говоря, не является КС-языком, но можно доказать более слабое утверждение: пересечение КС-языка с регулярным языком есть КС-язык.


Суперпозиция языков


Начнем с определения новой операции над языками — операции суперпозиции.


Пусть V=\{a_1,\ldots,a_n\} — произвольный алфавит, каждой букве a_i которого сопоставлен однозначно некоторый алфавит V_{a_i} (не исключено, что все алфавиты V,V_{a_1},\ldots,V_{a_n} совпадают); в алфавите V фиксируем произвольно язык L\subseteq V_{a_i}^{\ast}, а в каждом из алфавитов V_{a_i} — язык L_{a_i}\subseteq V_{a_i}^{\ast}.


Рассмотрим множество всех таких цепочек в объединении алфавитов V_{a_1}\cup\ldots\cup V_{a_n}, которые могут быть получены из цепочек языка L следующим образом: берем произвольную цепочку b_1\ldots b_k\in L и каждую букву b_j в ней заменяем произвольной цепочкой x_j\in L_{b_j}\colon


\begin{array}{cccc}b_1&\quad b_2&\quad \ldots&\quad b_k\\ \downarrow&\quad \downarrow&\quad &\downarrow\\ x_1&\quad x_2&\quad \ldots&\quad x_k \end{array}

в результате чего получаем цепочку x_1x_2\ldots x_k.


Множество всех цепочек вида x_1x_2\ldots x_k, получаемых описанным выше способом, называют суперпозицией (или подстановкой) языков L_{a_1},\ldots,L_{a_n} в язык L и обозначают \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}). При этом полагают, что если пустая цепочка \lambda принадлежит языку L, то она принадлежит суперпозиции \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}).


При определении суперпозиции на алфавиты V,V_{a_1},\ldots,V_{a_n} не накладывается никаких ограничений. Они могут и попарно не пересекаться, а могут и все совпадать. В любом случае суперпозиция \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}) есть язык в алфавите V_{a_1}\cup\ldots\cup V_{a_n}. Точно так же среди языков L_{a_i}, "подставляемых" в язык L, может оказаться и сам язык L, т.е. язык можно подставлять сам в себя, причем многократно.


Заметим, что если язык L не содержит пустую цепочку, суперпозиция \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}) может ее содержать. Это возможно, если каждый язык L_{a_i} содержит пустую цепочку. Тогда, беря произвольно x\in L и заменяя каждый ее символ пустой цепочкой, получаем пустую цепочку как элемент суперпозиции. Если же пустая цепочка принадлежит L, то, по определению, суперпозиция обязана ее содержать.


Еще заметим, что для разных вхождений одной и той же буквы b_j цепочки x\in L совершенно не обязательно заменять эту букву одной и той же цепочкой языка L_{b_j}: каждому вхождению может быть сопоставлена своя цепочка этого языка.




Пример 8.18. Зададим язык L в алфавите V=\{a,b,c\} как множество \{a^nb^nc^n\colon n\geqslant1\}. Букве a алфавита V сопоставим алфавит V_a=\{0;1\}, выбрав в качестве языка L_a множество \{0^n1^n\}_{n\geqslant0}. Букве b\in V сопоставим алфавит V_b=\{a\} и в этом алфавите — язык L_b=\{a^{n^2}\colon n\geqslant0\}. Наконец, букве c алфавита V сопоставим алфавит V_c=\{a,b,c\}=V и в качестве языка L_c возьмем язык L, пополненный пустой цепочкой, т.е. L_c=\{a^nb^nc^n\colon n\geqslant0\}.


Возьмем цепочку aabbcc\in L и первый символ а заменим цепочкой 0011\in L_a, второй символ a — цепочкой 01\in L_a, первый символ b — цепочкой a^{729}\in L_a (при n=27), второй символ b — пустой цепочкой, первый символ c — пустой цепочкой, второй символ — цепочкой abc\in L_c. В результате получим следующую цепочку, принадлежащую суперпозиции \mathcal{S}(L,L_a,L_b,L_c)\colon


001101a^{729}abc= 001101\underbrace{aaa\ldots aa}_{729\,\text{times}} abc.

Проделывая аналогичные действия с любой другой цепочкой языка L или же производя другие замены символов той же самой цепочки, будем получать все новые цепочки определенной выше суперпозиции. В данном случае будем иметь \lambda\in \mathcal{S}(L,L_a,L_b,L_c), так как каждый из языков L_a,\,L_b и L_c содержит пустую цепочку.


Пример 8.19. Пусть алфавит V есть русский алфавит {A,Б,..,Э,Ю,Я}, а язык L — множество всех слов русского языка. Каждой букве русского алфавита сопоставим язык, состоящий из единственной однобуквенной цепочки \alpha, которая стоит рядом с указанной русской буквой на клавиатуре компьютера. Так, L_A=\{F\},~ L_B=\{<\} и т.д. Все эти языки можно считать языками в латинском алфавите, дополненном определенными специальными символами, такими, как [,],\{,\},<,< и т.п. Тогда, если мы в качестве исходной цепочки языка L возьмем слово УЧЕБНИК, то получим такую цепочку в суперпозиции \mathcal{S}(L,L_A,\ldots)\colon\, EXT<YBR.


Разобранные примеры показывают, что суперпозицию можно рассматривать как своего рода "кодирование" цепочек языка L с заменой в них каждой буквы цепочкой другого языка. Действительно, такая замена является одним из простейших способов "шифровки" текстов.


Замечание 8.11. Суперпозицию можно определить через соответствие. Введем соответствие \sigma\subseteq V\times \{L_{a_1}\cup\ldots\cup L_{a_n}\} так, что для каждого i=\overline{1,n} упорядоченная пара (a_i,y) принадлежит а тогда и только тогда, когда y\in L_{a_i}. В этом случае


\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})= \bigcup\limits_{x\in L\setminus \{\lambda\}} \sigma\bigl(x(1)\bigr)\ldots \sigma\bigl(x(k)\bigr)\cup (\{\lambda\}\cap L), где x=x(1)\ldots x(k).

В терминах суперпозиции могут быть представлены такие операции над языками как объединение, соединение и итерация.




Объединение языков


Пусть L_1 и L_2 — два произвольных языка в каком-то алфавите W. Возьмем произвольный двухбуквенный алфавит V=\{a,b\} и язык L зададим как L=V (т.е. язык L состоит из двух однобуквенных цепочек a и b). Рассмотрим суперпозицию \mathcal{S}(L,L_a,L_b), где L_a=L_1,~L_b=L_2. Докажем, что эта суперпозиция совпадает с объединением L_1\cup L_2. Действительно, если мы возьмем цепочку a\in L, то ее единственную букву мы можем, согласно определению суперпозиции, заменить любой цепочкой языка L_1. Точно так же, строя суперпозицию, вместо цепочки b\in L получим все цепочки языка L_2. Итак,


L_1\cup L_2=\mathcal{S}\bigl(\{a,b\},L_1,L_2\bigr).



Соединение языков


Снова фиксируем произвольно в произвольном алфавите W языки L_1 и L_2. Опять-таки произвольно выберем двухбуквенныи алфавит \{a,b\}, определив язык L=\{ab\}. Положим, как и выше, L_a=L_1,~L_b=L_2. Тогда суперпозиция \mathcal{S}(L,L_a,L_b)= \mathcal{S}(\{ab\},L_a,L_b) совпадет с соединением L_1L_2. В самом деле, символ a единственной цепочки ab языка L можно при построении суперпозиции заменять любой цепочкой языка L_1, а символ b — любой цепочкой языка L_2. В результате записанная выше суперпозиция совпадет с множеством всех цепочек, представимых как соединение xy, где x\in L_1,~y\in L_2. Но это и есть соединение L_1L_2. Итак,


L_1L_2=\mathcal{S}\bigl(\{ab\},L_1,L_2\bigr).



Итерация языков


Рассуждая аналогично, можно показать, что итерация L^{\ast} языка L равна


L^{\ast}=\mathcal{S}(a^{\ast},L), а позитивная итерация L^{+}=\mathcal{S}(a^{+},L)

(для любых алфавита W, языка L\subseteq W^{\ast} и однобуквенного алфавита V=\{a\}).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved