Гомоморфизмы

Гомоморфизм цепочек — это такая функция на множестве цепочек, которая подставляет определенную цепочку вместо каждого символа данной цепочки.

Пример 4.13. Функция h, определенная как h(0) = ab и h(1) = , является гомоморфизмом. В любой цепочке из символов 0 и 1 h заменяет все нули цепочкой ab, а все единицы — пустой цепочкой. Например, применяя h к цепочке 0011, получим abab. Формально, если h есть некоторый гомоморфизм на алфавите V, а w = a1a2…an — цепочка символов в V, то h(w) = h(a1)h(a2)…h(an). Таким образом, сначала h применяется к каждому символу цепочки w, а потом полученные цепочки символов соединяются в соответствующем порядке. Например, рассмотрим гомомор физм h из примера и цепочку w = 0011: h(w) = h(0)h(0)h(1)h(1) = (ab)(ab)()() = abab, что и утверждается в этом примере.

Гомоморфизм языка определяется с помощью его применения к каждой цепочке языка, т.е. если L — язык в алфавите V, а h — гомоморфизм на , то h(L) = {h(w) | w принадлежит L}. Рассмотрим язык L регулярного выражения 10*1, т.е. все цепочки, которые начинаются и заканчиваются единицей, а между ними содержат произвольное число нулей.

Пусть h — гомоморфизм из примера. Тогда h(L) — это язык выражения (ab)*. Объясняется это тем, что h исключает все единицы, заменяя их пустыми символами., а вместо каждого нуля подставляет цепочку ab. Идея применения гомоморфизма непосредственно к регулярному выражению используется для доказательства замкнутости регулярных языков относительно гомоморфизма.

Теорема Если L — регулярный язык в алфавите V, а h — гомоморфизм на V, то язык h(L) также регулярен.

Доказательство. Пусть L = L(R) для некоторого регулярного выражения R. Вообще, если E есть регулярное выражение с символами из алфавита V, то пусть h(E) — выражение, полученное в результате замены каждого символа a в выражении E цепочкой h(a).

Утверждается, что выражение h(R) определяет язык h(L).

Это легко доказать с помощью структурной индукции. Если применить гомоморфизм h к любому подвыражению E выражения R, то язык выражения h(E) совпадет с языком, полученным в результате применения этого гомоморфизма к языку L(E). Формально,

L(h(E)) = h(L(E)).

Базис. Если E есть пустой символ, то h(E) совпадает с E, поскольку h не влияет на цепочку или язык. Следовательно, L(h(E)) = L(E). В то же время, если E равно пустому символу то L(E) либо не содержит ни одной цепочки, либо состоит из цепочки без символов. Таким образом, в обоих случаях h(L(E)) = L(E). Из этого следует, что L(h(E)) = L(E) = h(L(E)).

Возможен еще один базисный вариант, когда E = a для некоторого символа a . В этом случае L(E) = {a}, и h(L(E)) = {h(a)}. Выражение h(E) представляет собой цепочку символов h(a). Таким образом, язык L(h(E)) также совпадает с {h(a)}, и, следовательно,

L(h(E)) = h(L(E)).

Индукция. В зависимости от операции в регулярном выражении возможны три ситуации. Все они просты, поэтому обоснуем индукцию только для объединения, E = F + G.

Способ применения гомоморфизмов к регулярным выражениям гарантирует, что h(E) = h(F + G) = h(F) + h(G).

Нам также известно, что L(E) = L(F) U L(G) и L(h(E)) = L(h(F) + h(G)) = L(h(F)) U L(h(G)) (4.2) по определению операции + для регулярных выражений. Наконец, h(L(E)) = h(L(F) U L(G)) = h(L(F)) U h(L(G)), (4.3) поскольку h применяется к языку путем применения его к каждой цепочке этого языка по отдельности. По индуктивной гипотезе L(h(F)) = h(L(F)) и L(h(G)) = h(L(G)).

Таким образом, правые части выражений (4.2) и (4.3) эквивалентны, и, следовательно,

L(h(E)) = h(L(E)).

Для случаев, когда выражение E является конкатенацией или итерацией, доказательства не приводятся, поскольку они аналогичны доказательству, представленному выше.

Итак, можно сделать вывод, что L(h(R)) действительно равняется h(L(R)), т.е. применение гомоморфизма к регулярному выражению языка L дает регулярное выражение, определяющее язык h(L).