Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-06-25 | 364 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим пересечение двух регулярных языков. Здесь почти нечего делать, поскольку операции объединения, дополнения и пересечения не являются независимыми. Пересечение языков L и M выражается через объединение и дополнение следующим тождеством.
Вообще, пересечение двух множеств — это множество элементов, не принадлежащих дополнениям каждого из них. Это замечание, записанное в виде равенства, представляет один из законов Де Моргана.
Другой закон имеет аналогичный вид, только объединение и пересечение меняются местами, т.е.
Вместе с тем, для пересечения двух регулярных языков можно построить ДКА непосредственно. Конструкция произведения формально представлена в следующей теореме.
Автомат, имитирующий два других автомата и допускающий тогда и только тогда, когда допускают оба автомата
Теорема. Если L и M — регулярные языки, то язык L ∩ M также регулярен. На рис., представлен автомат — произведение двух данных автоматов. Его состояния помеченыкак пары состояний исходных автоматов.
Легко доказать, что этот автомат допускает пересечение первых двух языков, т.е. те цепочки, которые содержат как 0, так и 1. Состояние pr представляет начальное условие, когда на вход автомата пока не поступили ни 0, ни 1. Состояние qr означает, что поступили только нули, а состояние ps — только единицы. Допускающее состояние qs представляет условие того, что на вход автомата поступили и нули, и единицы
Замкнутость относительно разности
Существует еще одна, четвертая, операция, часто применяемая к множествам и связанная с булевыми операциями, а именно, разность множеств. В терминах языков разностью L – M языков L и M называют множество цепочек, которые принадлежат L и не принадлежат M. Регулярные языки замкнуты относительно этой операции. Доказательство замкнутости относительно разности следует из доказанных выше теорем
|
Доказательство. Заметим, что . По теореме 4.5 регулярен язык , а по теореме 4.8 . Следовательно, язык L – M регулярен.[2]
Обращение
Обращением цепочки a1a2 … an называется цепочка, записанная в обратном порядке,т.е. anan-1 … a1. Обращение w обозначается w R. Таким образом, 0010R есть 0100, а R = . Обращение языка L, обозначаемое L R, состоит из всех цепочек, обратных цепочкам языка L. Например, если L = {001, 10, 111}, то L R = {100, 01, 111}.
Обращение является еще одной операцией, сохраняющей регулярность языков, т.е. если язык L регулярен, то L R также регулярен. Это легко доказать двумя способами, первый из которых основан на автоматах, а второй — на регулярных выражениях. Доказательство, основанное на автоматах, приводится неформально.
Затем приводится формальное доказательство, использующее регулярные выражения.
Если задан язык L, который есть L (A) для некоторого конечного автомата A, вероятно, с недетерминизмом и -переходами, то можно построить автомат для L R следующим образом.
1. Обратить все дуги на диаграмме переходов автомата A.
2. Сделать начальное состояние автомата A единственным допускающим состоянием нового автомата.
3. Создать новое начальное состояние p0 с -переходами во все допускающие состоя-
4. ния автомата A.
В результате получим автомат, имитирующий автомат A “в обратном порядке” и, следовательно, допускающий цепочку w тогда и только тогда, кода A допускает w R.
Пример. (0+1)0*
Гомоморфизмы
Гомоморфизм цепочек — это такая функция на множестве цепочек, которая подставляет определенную цепочку вместо каждого символа данной цепочки.
Пример 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).[3]
Обратный гомоморфизм
Гомоморфизм можно применять “назад”, и это также сохраняет регулярность языков.
Предположим, что h — гомоморфизм в алфавите V
Пусть L — язык в алфавите T. Тогда h -1(L), читаемое как“обратное h от L ”, — это множество цепочек w из V*, для которых h (w) принадлежит L.
Пример 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. [8]
Достаточность. Предположим, что цепочка 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.[5]
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!