dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 35
Текст из файла (страница 35)
154ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ3.Создать новое начальное состояние p0 с ε-переходами во все допускающие состояния автомата A.В результате получим автомат, имитирующий автомат A “в обратном порядке” и, следовательно, допускающий цепочку w тогда и только тогда, кода A допускает wR.Теперь докажем теорему для обращения формально.Теорема 4.11.
Если язык L регулярен, то язык LR также регулярен.Доказательство. Предположим, что язык L определяется регулярным выражением E.Доказательство проводится структурной индукцией по длине выражения E. Покажем,что существует еще одно регулярное выражение ER, для которого L(ER) = (L(E))R, т.е.язык выражения ER является обращением языка выражения E.Базис. Если E равно ε, ∅ или a, где a — некоторый символ, то ER совпадает с E, т.е.{ε}R = {ε}, ∅R = ∅ и {a}R = {a}.Индукция. В зависимости от вида выражения E возможны три варианта.1.E = E1 + E2. Тогда ER = E1R + E2R. Доказательство состоит в том, что обращение объединения двух языков получается, если сначала вычислить, а затем объединить обращения этих языков.2.E = E1E2.
Тогда ER = E2RE1R. Заметим, что необходимо обратить не только сами языки, но и их порядок. Например, если L(E1) = {01, 111}, а L(E2) = {00, 10}, тоL(E1E2) = {0100, 0110, 11100, 11110}. Обращение этого языка есть {0010, 0110,00111, 01111}.Если соединить обращения языков L(E2) и L(E1) в таком порядке, как они здесь записаны, то получим язык{00, 01}{10, 111} = {0010, 00111, 0110, 01111},который равен языку (L(E1E2))R. В общем случае, если цепочка w из L(E) являетсяконкатенацией цепочек w1 из L(E1) и w2 из L(E2) , то wR = w2Rw1R.3.E = E1*. Тогда ER = (E1R)*.
Доказательство состоит в том, что любая цепочка w изL(E) может быть записана как w1w2…wn, где каждая wi принадлежит L(E). НоwR = wnRwn–1R…w1R.Каждая wiR принадлежит L(ER), т.е. wR принадлежит (E1R)*. И наоборот, любая цепочка из L((E1R)*) имеет вид w1w2…wn, где каждая цепочка wi является обращениемнекоторой цепочки из L(E1). Следовательно, обращение данной цепочки wnRwn–R*R1 …w1 принадлежит языку L(E1 ), который равен L(E).
Таким образом, доказано,что цепочка принадлежит L(E) тогда и только тогда, когда ее обращение принадлежит L((E1R)*).Пример 4.12. Пусть язык L определяется регулярным выражением (0 + 1)0*. Тогдасогласно правилу для конкатенации LR — это язык выражения (0*)R(0 + 1)R. Если приме4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 155155нить правила для итерации и объединения к двум частям этого выражения, а потом использовать базисное правило, которое говорит, что обратными к 0 и 1 будут эти же выражения, то получим, что язык LR определяется регулярным выражением 0*(0 + 1). 4.2.3. ÃîìîìîðôèçìûГомоморфизм цепочек — это такая функция на множестве цепочек, которая подставляет определенную цепочку вместо каждого символа данной цепочки.Пример 4.13.
Функция h, определенная как h(0) = ab и h(1) = ε, является гомоморфизмом. В любой цепочке из символов 0 и 1 h заменяет все нули цепочкой ab, а все единицы — пустой цепочкой. Например, применяя h к цепочке 0011, получим abab. Формально, если h есть некоторый гомоморфизм на алфавите Σ, а w = a1a2…an — цепочка символов в Σ, то h(w) = h(a1)h(a2)…h(an).
Таким образом, сначала h применяется ккаждому символу цепочки w, а потом полученные цепочки символов соединяются в соответствующем порядке. Например, рассмотрим гомоморфизм h из примера 4.13 и цепочку w = 0011: h(w) = h(0)h(0)h(1)h(1) = (ab)(ab)(ε)(ε) = abab, что и утверждается в этомпримере.Гомоморфизм языка определяется с помощью его применения к каждой цепочке языка, т.е. если L — язык в алфавите Σ, а h — гомоморфизм на Σ, то h(L) = {h(w) | w принадлежит L}. Рассмотрим язык L регулярного выражения 10*1, т.е. все цепочки, которые начинаются и заканчиваются единицей, а между ними содержат произвольное число нулей.Пусть h — гомоморфизм из примера 4.13. Тогда h(L) — это язык выражения (ab)*. Объясняется это тем, что h исключает все единицы, заменяя их ε, а вместо каждого нуля подставляет цепочку ab.
Идея применения гомоморфизма непосредственно к регулярномувыражению используется для доказательства замкнутости регулярных языков относительно гомоморфизма.Теорема 4.14. Если L — регулярный язык в алфавите Σ, а h — гомоморфизм на Σ, тоязык h(L) также регулярен.Доказательство. Пусть L = L(R) для некоторого регулярного выражения R. Вообще,если E есть регулярное выражение с символами из алфавита Σ, то пусть 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)).156Стр. 156ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂВозможен еще один базисный вариант, когда 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). 4.2.4. Îáðàòíûé ãîìîìîðôèçìГомоморфизм можно применять “назад”, и это также сохраняет регулярность языков.Предположим, что h — гомоморфизм из алфавита Σ в цепочки, заданные в другом(возможно, том же) алфавите T4. Пусть L — язык в алфавите T. Тогда h-1(L), читаемое как“обратное h от L”, — это множество цепочек w из Σ*, для которых h(w) принадлежит L.На рис. 4.5, а представлено применение гомоморфизма к языку L, а на рис.
4.5, б — использование обратного гомоморфизма.Пример 4.15. Пусть L — язык регулярного выражения (00 + 1)*, т.е. все цепочки изсимволов 0 и 1, в которых нули встречаются парами. Таким образом, цепочки 0010011 и10000111 принадлежат L, а 000 и 10100 — нет.Пусть h — такой гомоморфизм: h(a) = 01, h(b) = 10. Утверждается, что h–1(L) — этоязык регулярного выражения (ba)*, т.е. все цепочки, в которых повторяются пары ba. Докажем, что h(w) принадлежит L тогда и только тогда, когда цепочка w имеет вид baba…ba.4Под “Т” подразумевается прописная буква греческого алфавита “тау”, следующая за буквой “сигма”.4.2.
ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 157157а)б)Рис. 4.5. Гомоморфизм, применяемый в прямом и обратном направленииДостаточность. Предположим, что цепочка w состоит из n повторений ba для некоторого n ≥ 0. Заметим, что h(ba) = 1001, т.е. h(w) — это n повторений цепочки 1001. Поскольку цепочка 1001 построена из двух единиц и пары нулей, то она принадлежит языкуL. Следовательно, цепочка, состоящая из любого числа повторений 1001, также образована единицами и парами нулей и принадлежит L.
Таким образом, h(w) принадлежит L.Необходимость. Теперь предположим, что h(w) принадлежит L, и покажем, что цепочка w имеет вид baba…ba. Существует четыре условия, при которых цепочка имеетдругой вид. Покажем, что при выполнении любого из них h(w) не принадлежит L, т.е.
докажем утверждение, противоположное тому, что нам нужно доказать.1.Если w начинается символом а, то h(w) начинается с 01. Следовательно, она содержит отдельный 0 и поэтому не принадлежит L.2.Если w заканчивается символом b, то в конце h(w) стоит 10, и опять-таки в цепочкеh(w) есть изолированный 0.3.Если в цепочке w дважды подряд встречается a, то h(w) содержит подцепочку 0101.Снова в w есть изолированный нуль.4.Аналогично, если в w есть два символа b подряд, то h(w) содержит подцепочку 1010с изолированным 0.158Стр. 158ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂТаким образом, при выполнении хотя бы одного из вышеперечисленных условий цепочка h(w) не принадлежит L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
