Свойство замкнутости регулярных языков

Содержание

Введение. 2

1 Свойство замкнутости регулярных языков. 4

1.1 Замкнутость относительно булевых операций. 4

1.2 Обращение. 8

1.3 Гомоморфизмы.. 9

1.4 Обратный гомоморфизм. 11

2 Свойства разрешимости регулярных языков. 12

2.1 Преобразования различных представлений языков. 12

2.2 Проверка пустоты регулярных языков. 15

2.3 Проверка принадлежности регулярному языку. 16

Заключение. 20

Список литературы.. 21

Введение

Формальные языки очень важны в современном мире. В прежние времена под языками подразумевалось исключительно средство общения между людьми, то есть имелись в виду только естественные языки – русский, немецкий, английский и др. В начале ХХ века — это представление претерпело серьёзные изменения и в настоящее время под языком понимается всякое средство общения, состоящее из знаковой системы, множества смыслов этой системы и имеющее установленное соответствие между последовательностями знаков и смыслами. С развитием науки и техники появились формальные языки и сегодня их используют специалисты в различной профессиональной деятельности. Формальными языками являются системы математических, химических символов, азбука Морзе, нотная грамота и множество других. Формальные языки используют не только специалисты в каких-то профессиях. Например, повсеместно используемая десятичная система счисления или шрифт Брайля также являются формальными языками. С точки зрения информатики важную роль играют такие формальные языки как язык алгебры логики и языки программирования.

Отличительная особенность формальных языков от естественных заключается в том, что правила формальных языков задаются в явной форме, а смысл и значение знаков не меняется в зависимости от каких-либо прагматических обстоятельств, например, от контекста. Коротко говоря, формальный язык - это строгая математическая модель реального языка, где под реальным языком понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, то есть образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями.

Среди формальных языков важное место занимает класс регулярных языков. Это самый простой тип языков и, благодаря этому, самый широко используемый в области вычислительных систем.

Распознавателем для регулярных языков являются односторонние недетерминированные автоматы без внешней памяти – конечные автоматы. Время на разбор предложений регулярного языка линейно зависит от длины входной цепочки символов. Кроме того, любой недетерминированный конечный автомат можно преобразовать в детерминированный, что существенно упрощает разработку программного обеспечения, обеспечивающего функционирование распознавателя. Благодаря высокой скорости работы и простоте распознавателя регулярные языки получили широкую область применения. Регулярные языки используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д. Кроме того, они лежат в основе многих мнемокодов машинных команд (языки ассемблеров), на них строятся командные процессоры, символьные управляющие команды и другие подобные структуры. В компиляторах распознаватели на основе регулярных языков используются для лексического анализа входного языка – выделения в нём простейших лексем. Для регулярных языков существует множество математически обоснованных методов и алгоритмов.

Актуальность исследования: Знакомство студентов с формальными языками зачастую начинается именно с регулярных языков, поэтому понимание описанных в данной работе преобразований чрезвычайно важно для дальнейшего обучения.

Цель исследования - изучить основные свойства регулярных языков.

Предметом исследования является свойства регулярных языков.

Объектом исследования являются регулярные языки.

Обращение

Обращением цепочки a1a2…an называется цепочка, записанная в обратном порядке,т.е. anan-1…a1. Обращение w обозначается wR. Таким образом, 0010R есть 0100, а R = . Обращение языка L, обозначаемое LR, состоит из всех цепочек, обратных цепочкам языка L. Например, если L = {001, 10, 111}, то LR = {100, 01, 111}.

Обращение является еще одной операцией, сохраняющей регулярность языков, т.е. если язык L регулярен, то LR также регулярен. Это легко доказать двумя способами, первый из которых основан на автоматах, а второй — на регулярных выражениях. Доказательство, основанное на автоматах, приводится неформально.

Затем приводится формальное доказательство, использующее регулярные выражения.

Если задан язык L, который есть L(A) для некоторого конечного автомата A, вероятно, с недетерминизмом и -переходами, то можно построить автомат для LR следующим образом.

1. Обратить все дуги на диаграмме переходов автомата A.

2. Сделать начальное состояние автомата A единственным допускающим состоянием нового автомата.

3. Создать новое начальное состояние p0 с -переходами во все допускающие состоя-

4. ния автомата A.

В результате получим автомат, имитирующий автомат A “в обратном порядке” и, следовательно, допускающий цепочку w тогда и только тогда, кода A допускает wR.

Пример. (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]

Заключение

Существует много операций, результат применения которых к регулярным языкам также является регулярным языком. В их числе объединение, конкатенация, замыкание (итерация), пересечение, дополнение, разность, обращение, гомоморфизм (замена каждого символа соответствующей цепочкой) и обратный гомоморфизм. Конечные автоматы, безусловно, полезны для реализации логики искусственного интеллекта в играх. Они могут быть легко представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.

Существует алгоритм, который по такому заданному представлению регулярного языка, как автомат или регулярное выражение, определяет, является ли представленный язык пустым множеством.

Существует алгоритм, который по заданной цепочке и некоторому представлению регулярного языка определяет, принадлежит ли цепочка языку.

Реализация конечного автомата с функциями-состояниями является простым, но в то же время мощным методом. Даже более сложные переплетения состояний могут быть реализованы при помощи FSM.

Список литературы

1. Карпов Ю. Теория автоматов. – СПб.: Питер, 2002. - 224 с.

2. Хопкрофт Д. и др. Введение в теорию автоматов, языков и вычислений. – М.: Вильямс, 2002.

3. Гордеев А., Молчанов Ю. Системное программное обеспечение. – СПб.: Питер, 2001. - 736 c.

4. Гинзбург С., Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. - Кибернетический сборник, Новая серия, вып. 5. - М.: Мир, 1968. - С. 138-166.

5. Хопкрофт Дж. Алгоритм для минимизации конечного автомата. - Кибернетический сборник, Новая серия, вып. 11. - М.: Мир, 1974. - С. 177–184.

6. Клини С.К. Представление событий в нервных сетях. - сб. “Автоматы”. - М.: ИЛ, 1956. - С. 15–67.

7. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. — сб. “Автоматы”. — М.: ИЛ, 1956. — С. 179–210.

8. http://www.quizful.net/post/Java-RegExp

9. https://ru.wikipedia.org

Содержание

Введение. 2

1 Свойство замкнутости регулярных языков. 4

1.1 Замкнутость относительно булевых операций. 4

1.2 Обращение. 8

1.3 Гомоморфизмы.. 9

1.4 Обратный гомоморфизм. 11