Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 35
Текст из файла (страница 35)
Если соединить обрашения языков ЦЕз) и Е(Е,) в таком порядке, как они здесь записаны, то получим язык (00, О1)(!О, 111) = (0010, 00111, 0110, 011!1), который равен языку (Е(Е,Ег)~3. В обшем случае, если цепочка и из ЦЕ) является конкатенацией цепочек и ~ из ЦЕ~) и из из Е(Е,), то и = из ич . к к к 3. Е=Е, . Тогда Е =(Е, ) . Доказательство состоит в том, что любая цепочка и из к к~ ЦЕ) может быть записана как иэи л,.эк„, где каждая и, принадлежит ЦЕ).
Но к Каждая и,к принадлежит ЦЕк), т.е. ив принадлежит (Е,к) . И наоборот, любая цепочка из Ц(Е, ) ) имеет вид ю,зк,...ик„, где каждая цепочка и, является обращением некоторой цепочки из Е(Е~). Следовательно, обращение данной цепочки и„~зк„ ~ ...ич принадлежит языку Е(Е, ), который равен Е(Е). Таким образом, доказано, что цепочка принадлежит ЦЕ) тогда и только тогда, когда ее обращение принадле- жигЦ(Е~ ) ). ьЗ Пример 4.12. Пусть язык Е определяется регулярным выражением (О+ 1)0 .
Тогда согласно правилу для конкатенации Š— это язык выражения (О ) (О+ 1) . Если примек ' к к 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ нить правила для итерации и объединения к двум частям этого выражения, а потом использовать базисное правило, которое говорит, что обратными к 0 и 1 будут эти же выражения, то получим, что язык Ек определяется регулярным выражением 0 (О + 1). С3 4,2.3.
ГОМОМОРфИЗМЫ Гомоморфизм цепочек — это такая функция на множестве цепочек, которая подставляет определенную цепочку вместо каждого символа данной цепочки. Пример 4.13.Функция Ь, определенная как Ь(0) = аЬ и Ь(1)=в, является гомоморфизмом. В любой цепочке из символов 0 и 1 Ь заменяет все нули цепочкой а6, а все единицы — пустой цепочкой. Например, применяя Ь к цепочке 00 ! 1, получим аЬаЬ. П Формально, если Ь есть некоторый гомоморфизм на алфавите Е, а ж = а~ад..а„— цепочка символов в Т., то Ь(зк) = Ь(а,)Ь(и,)...Ь(а„).
Таким образом, сначала Ь применяется к каждому символу цепочки ж, а потом полученные цепочки символов соединяются в соответствующем порядке. Например, рассмотрим гомоморфизм Ь из примера 4.!3 и цепочку и = 0011: Ь(и ) = Ь(0)Ь(0)Ь(1)Ь(! ) = (аЬ)(аЬ)(а)(в) = аЬаЬ, что и утверждается в этом примере. Гомоморфизм языка определяется с помощью его применения к каждой цепочке языка, т,е. если Š— язык в алфавите а,, а Ь вЂ” гомоморфизм на Т,, то 6(Е) = (Ь(ж) ! ж принадлежит Ц.
Рассмотрим язык Е регулярного выражения 10 1, т.е. все цепочки, которые начинаются и заканчиваются единицей, а между ними содержат произвольное число нулей. Пусть Ь вЂ” гомоморфизм из примера 4. 13. Тогда Ь(Е) — это язык выражения (аЬ)*. Объясняется это тем, что Ь исключает все единицы, заменяя их в, а вместо каждого нуля подставляет цепочку аЬ. Идея применения гомоморфизма непосредственно к регулярному выражению используется для доказательства замкнутости регулярных языков относительно гомоморфизма. Теорема 4.14.
Если Š— регулярный язык в алфавите Т., а Ь вЂ” гомоморфизм на Т., то язык Ь(Е) также регулярен. Доказательство. Пусть Е = ЦЕ) для некоторого регулярного выражения !!. Вообще, если Е есть регулярное выражение с символами из алфавита Х, то пусть Ь(Е) — выражение, полученное в результате замены каждого символа а в выражении Е цепочкой Ь(а). Утверждается, что выражение Ь(Е) определяет язык Ь(Е). Это легко доказать с помощью структурной индукции.
Если применить гомоморфизм Ь к любому подвыражению Е выражения Е, то язык выражения Ь(Е) совпадет с языком, полученным в результате применения этого гомоморфизма к языку ЦЕ). Формально, ЦЬ(Е)) = Ь(ЦЕ)). Базис. Если Е есть к или И, то Ь(Е) совпадает с Е, поскольку Ь не влияет на цепочку в или язык И. Следовательно, ЦЬ(Е)) = Е(Е). В то же время, если Е равно Я или в, то ЦЕ) либо не содержит ни одной цепочки, либо состоит из цепочки без символов.
Таким образом, в обоих случаях Ь(ЦЕ)) = ЦЕ). Из этого следует, что Е(Ь(Е)) = Е(Е) = Ь(ЦЕ)). ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 15б Возможен еще один базисный вариант, когда Е = а для некоторого символа а из з.. В этом случае Е(Е) = (а), и Ь(ЦЕ)) = (6(а)). Выражение 6(Е) представляет собой цепочку символов 6(а). Таким образом, язык Ц6(Е)) также совпадает с (6(а)), и, следовательно, ЦЬ(Е)) = 6(Е(Е)). Иидукция. В зависимости от операции в регулярном выражении возможны три ситуации. Все они просты, поэтому обоснуем индукцию только для объединения, Е = Е+ 6. Способ применения гомоморфнзмов к регулярным выражениям гарантирует, что Ь(Е) = 6(Е+ 6) = 6(Е) + 6(0), Нам также известно, что ЦЕ) = ЦЕ) () Цб) и ЦЬ(Е)) = ЦЬ(Е) и 6(б)) = ЦЬ(Е)) 0 Е(6(0)) (4.2) по определению операции + для регулярных выражений.
Наконец, (4.3) 6(Е(Е)) = 6(Е(Е) () Е(О» = 6(Е(г)) и 6(Е(су)) поскольку Ь применяется к языку путем применения его к каждой цепочке этого языка по отдельности. По индуктивной гипотезе Е(6(Е)) = 6(Е(Е)) и ЦЬ(б)) = 6(ЦС)). Таким образом, правые части выражений (4.2) и (4.3) эквивалентны, и, следовательно, Е(Ь(Е)) = Ь(ЦЕ)). Для случаев, когда выражение Е является конкатенацией или итерацией, доказательства не приводятся, поскольку они аналогичны доказательству, представленному выше. Итак, можно сделать вывод, что Е(6(Е)) действительно равняется 6(Е(Е)), т.е. применение гомоморфизма к регулярному выражению языка Е дает регулярное выражение, определяющее язык 6(Е).
С3 4.2.4. Обратный гомоморфнзм Гомоморфизм можно применять "назад", и это также сохраняет регулярность языков. Предположим, что Ь вЂ” гомоморфизм из алфавита Е в цепочки, заданные в другом (аозможно, том же) алфавите з". Пусть Š— язык в алфавите Т. Тогда Ь'(Е), читаемое как "обратное Ь от Е*', — это множество цепочек м из Е, для которых 6(и) принадлежит Е.
На рнс. 4.5, а представлено применение гомоморфизма к языку Е, а на рис. 4.5, б — использование обратного гомоморфизма. Пример 4.15. Пусть Š— язык регулярного выражения (00+ 1), т.е. все цепочки из символов 0 и 1, в которых нули встречаются парами. Таким образом, цепочки 0010011 и 10000111 принадлежат Е, а 000 и 10100 — нет.
Пусть Ь вЂ” такой гомоморфизм: 6(а) = 01, 6(Ь) = 1О. Утверждается, что Ь '(Е) — это язык регулярного выражения (Ьа)*, т.е. все цепочки, в которых повторяются пары Ьа. Докажем, что Ь(ж) принадлежитЕ тогда и только тогда, когда цепочка и имеет вид ЬаЬа...Ьц. ' Под "'Г' подразумевается прописная буква греческого алфавита "тау", слелуюшая за буквой "сигма". 4,2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 157 Рис.
4.5. Гомоморфизм. примвиявмый в прямом и обратиам иаправявиии Достаточность. Предположим, что цепочка лв состоит из и повторений Ьа для некоторого и > О. Заметим, что Ь(Ьи) = 1001, т.е. Ь(лв) — это п повторений цепочки 1001. Поскольку цепочка ! 001 построена из двух единиц и пары нулей, то она принадлежит языку Ь. Следовательно, цепочка, состоящая из любого числа повторений 1001, также образована единицами и парами нулей и принадлежит Ь.
Таким образом, Ь(и ) принадлежит Р.. Необходимость. Теперь предположим, что Ь(ж) принадлежит Ь, и покажем, что цепочка ки имеет вид ЬаЬа...Ьа. Существует четыре условия, при которых цепочка имеет другой вид. Покажем, что при выполнении любого из них Ь(ж) не принадлежит ~., т.е, докажем утверждение, противоположное тому, что нам нужно доказать. !. Е сли и начинается символом и, то Ь(и ) начинается с 01. Следовательно, она содержит отдельный 0 и поэтому не принадлежит Ь.
2. Е сли и заканчивается символом Ь, то в конце Ь(ли) стоит 1О, и опять-таки в цепочке Ь(и) есть изолированный О. 3. Если в цепочке и дважды подряд встречается а, то Ь(ж) содержит подцепочку 0101. Снова в и есть изолированный нуль. 4. А налогично, если в ли есть два символа Ь подряд, то Ь(ли) содержит подцепочку 1010 с изолированным О. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ !58 Таким образом, при выполнении хотя бы одного из вышеперечисленных условий цепочка 6(и ) не принадлежит Г„Но если ни одно из условий 1-4 не выполняется, то цепочка и имеет внд ЬаЬа...ба.
Чтобы понять, почему это происходит, предположим, что ни одно нз зтнх условий не выполняется. Тогда невыполнение условия 1 означает, что и должна начинаться символом Ь, а невыполнение 2 — что она должна заканчиваться символом а. Невыполнение условий 3 и 4 говорит, что символы а и Ь должны чередоваться. Следовательно, логическое ИЛИ условий 1-4 эквивалентно утверждению "цепочка и имеет вид, отличный от ЬаЬа...Ьа". Но выше было доказано, что из логического ИЛИ условий 1-4 следует, что )т(те) не принадлежит Ь.
Это утверждение противоположно тому, что нужно доказать, а именно, что "если 6(и ) принадлежит Ь, то цепочка те имеет вид ЬаЬа...Ьа". П Далее докажем, что обратный гомоморфизм регулярного языка также регулярен, и покажем, как эту теорему можно использовать. Теорема 4.16. Если 6 — гомоморфизм из алфавита Е в алфавит Т, Š— регулярный язык иад Т, то язык 6 (Ь) также регулярен. Доказательство.
Начнем с ДКА А для языка Ь. По А и 6 строится ДКА для 6'(Ь) с помощью схемы, представленной на рис. 4.6. Этот ДКА использует состояния автомата А, но переводит входной символ в соответствии с 6 перед тем, как решить, в какое состояние перейти. Вход а Нач уститьуотвертиуть Рис. 4.6. ДКА для )т '(Ц применяет гомоморфизм 6 ко входным символам, о пот пи имитирует ДКА для Ь Формально, пусть Ь вЂ” это ь(А), где ДКА А = (Ь), Т, б, де, г").
Определим ДКА В=ЩЕ,у,д,,р), функция переходов у'которого строится по правилу )(т), а) = Б (д, 6(а)). Таким образом, переход автомата В по входному символу а является результатом последовательности переходов, совершаемых автоматом А при получении цепочки символов 6(а). Напомним, 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 159 что, хотя а(а) может равняться е, состоять из одного или нескольких символов, функция б определена так, чтобы справиться со всеми этими случаями.
С помощью индукции по [и[ легко показать, что у(д0, и) = б (ц,, Ь(и)), Поскольку допускающие состояния автоматов А и В совпадают, то В допускает цепочку и тогда и только тогда, когда А допускает цепочку й(ж), Иными словами, В допускает только те цепочки, которые принадлежат языку Уз ~(Ь). СЗ Пример 4.17. В этом примере обратный гомоморфизм и некоторые другие свойства замкнутости регулярных множеств используются для доказательства одного необычного свойства конечных автоматов. Предположим, что, допуская входную цепочку, некоторый автомат должен побывать в каждом состоянии хотя бы по одному разу. Точнее, допустим, что А = © Х, б, дж г) — ДКА, и нас интересует язык Ц состоящий из всех цепочек и в алфавите Х, для которых б (дж ж) принадлежит г, и для каждого состояния гу из Д существует некоторый префикс хя цепочки ж, для которого б (а„х~) = ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
