Свойства регулярных языков (1134638), страница 4
Текст из файла (страница 4)
Если 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ155нить правила для итерации и объединения к двум частям этого выражения, а потом использовать базисное правило, которое говорит, что обратными к 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ÃËÀÂÀ 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ157а)б)Рис.
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ÃËÀÂÀ 4.
ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂТаким образом, при выполнении хотя бы одного из вышеперечисленных условий цепочка h(w) не принадлежит L. Но если ни одно из условий 1–4 не выполняется, то цепочка wимеет вид baba…ba. Чтобы понять, почему это происходит, предположим, что ни одноиз этих условий не выполняется. Тогда невыполнение условия 1 означает, что w должнаначинаться символом b, а невыполнение 2 — что она должна заканчиваться символом a.Невыполнение условий 3 и 4 говорит, что символы a и b должны чередоваться. Следовательно, логическое ИЛИ условий 1–4 эквивалентно утверждению “цепочка w имеет вид,отличный от baba…ba”. Но выше было доказано, что из логического ИЛИ условий 1–4следует, что h(w) не принадлежит L. Это утверждение противоположно тому, что нужнодоказать, а именно, что “если h(w) принадлежит L, то цепочка w имеет вид baba…ba”.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
