ТМВ-2020-Семинар-18.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Регулярные языки

Пусть \(L\) — регулярный язык, тогда:

  • \(L^0=\{\varepsilon\} \);
  • \(LL\) — конкатенация;
  • \(L^{n+1}=LL^n\) — степень языка (определена по индукции);
  • \(L^*=\{\omega\in\Sigma\mid\exists n\in \mathbb{N_0} \; \omega\in L^n\}\) — итерация;
  • \(\overline{L}\) — регулярный язык.

Также верны следующие свойства замкнутости множества языков (\(L_1, L_2\) — регулярные языки):

  • \(L_1 \cap L_2\) — регулярный язык;
  • \(L_1 \cup L_2\) — регулярный язык;
  • \(L_1L_2\) — регулярный язык.

Замкнутость означает, что применение операций \(\cup,\cap,\cdot \) (объединения, пересечения, конкатенации) к элементам множества регулярных языков не выводит нас за пределы этого множества (т. е. полученный язык — регулярный).

Благодаря вышеизложенному мы можем использовать регулярные языки, для того чтобы определять новые регулярные языки. Подробнее разберёмся с языком регулярных выражений (РВ), научимся конвертировать КА в РВ и наоборот.

Регулярные выражения

Базовые регулярные выражения

Идея состоит в том, что у нас в языке РВ есть набор примитивов, операции над ними, благодаря которым можем определить некое РВ.

Набор примитивов:

  • \(\varepsilon(\lambda)\) — пустое слово;
  • \(a\in\Sigma\) — какая-то буква алфавита (сама определяет регулярный язык);
  • \(\varnothing\) — язык без слов (пустое множество).

Операции:

  • \(R_1+R_2\) — объединение;
  • \(R_1R_2\) — конкатенация;
  • \(R^*\) — итерация;
  • \((R)\) — взятие в скобки (необходимо для регулирования приоритета).

Язык регулярных выражений по индукции регулярен, т. к. базовые элементы (примитивы) регулярны, операции над элементами регулярны. Говорят, что регулярное выражение генерирует язык, в отличие от автомата, который его определяет.

Пример 1

Алфавит \(\Sigma = \{a,b\}\). Рассмотрим следующий язык \(L=\{\omega\in\Sigma^*\mid\omega\text{ содержит подстроку }aa\}\)

«Фундаментом» будет служить наше точное знание, что в \(\omega\) есть \(aa\). Также понятно, что до и после этой подстроки может быть любое количество символов. Это можно задать с помощью конструкции \((a+b)^*\). Тогда получим РВ для этого языка:\[(a+b)^*aa(a+b)^*\]

Также это выражение можно записать в следующем виде (зная, что \(a, b\) — все элементы алфавита \(\Sigma\)):\[\Sigma^*aa\Sigma^*\]

Пример 2

Алфавит \(\Sigma = \{a,b\}\). Рассмотрим следующий язык \(L=\{\omega\in\Sigma^*\mid\lvert\omega \rvert =4\}\)

Очевидно, что такой язык определит следующее РВ\(: \Sigma\Sigma\Sigma\Sigma\) или \(\Sigma^4\)

Пример 3

Алфавит \(\Sigma = \{a,b\}\). Рассмотрим следующий язык \(L=\{\omega\in\Sigma^*\mid\omega\text{ содержит не более одной буквы }a\}\)

РВ \(b^*(a+\varepsilon)b^*\) определит данный язык. Следующий «синтаксический сахар» упростит запись таких выражений \(a?=(a+\varepsilon)\). Следовательно, наше РВ примет вид\(: b^*a?b^*\).

Пример 4

Алфавит \(\Sigma = \{.,a,@\}\), здесь \(a\) — \(\forall\) буква (символ). Рассмотрим следующий язык \(L=\{\omega\in\Sigma^*\mid\omega\text{ определяет корректный адрес электронной почты}\}\)

Электронный адрес состоит из двух частей: до и после символа @. После @ располагается домен, который как минимум состоит из двух частей (разделяемых точками). В левой части может быть произвольное количество последовательностей символов, разделяемых точками. Получим следующее РВ:\[(aa^*.)^*aa^*@aa^*.aa^*(.aa^*)^*=\color{fuchsia}{[aa^*=a^+\: (a^+\stackrel{\mathrm{def}}{=}a^*\setminus\varepsilon)]}=(a^+.)^*a^+@a^+.a^+(.a^+)^*=(a^+.)^*a^+@a^+(.a^+)^+\]

Рис. 1 — Алгоритм Томпсона

Алгоритм Томпсона

Преобразование регулярного выражения в конечный автомат довольно простое. Все основные конструкции нам уже известны. Для построения НКА используются примитивы, изображённые на рис. 1. Соответственно, разбирая РВ по частям, строим из примитивов КА. Такой процесс называется алгоритмом Томпсона. Подробнее можно самостоятельно ознакомиться в Интернете.

Алгоритм удаления вершин

Рис. 2 — КА, преобразуемый в РВ

Рассмотрим обратную ситуацию, т. е. преобразование КА в РВ. Преобразуем автомат на рис. 2. Заметим, что на его связях находятся \(R_i\) — некие регулярные выражения. На самом деле, нам неважно, что написано на связях, т. к. алгоритм от этого не поменяется. Однако, помним из лекций про обобщённый конечный автомат, на связях которого могут быть регулярные выражения.

Наша цель: удалять вершины до тех пор, пока не останутся две вершины, соединённые одной связью неким РВ. Для этого нам необходимо дополнительное построение. Добавляем новые вершины: начальную (соединяем со старой \(\varepsilon\)-переходом) и конечную (из всех старых конечных вершин делаем \(\varepsilon\)-переходы в неё, и перестаём старые конечные вершины считать таковыми).

Далее начинаем процесс удаления вершин, причём нам нужно сохранить все пути, проходящие через каждую вершину. Последовательно процесс удаления изображён на следующих изображениях:

Т. к. \(\varepsilon L=L\varepsilon=L\), то наше РВ, полученное выше будет иметь вид:\[R_1^*R_2(R_3R_1^*R_2+R_4)^*\]

Связь между ДКА, НКА и РВ

На схеме ниже изображены связи между ДКА, НКА и РВ.

3 3 — Связь между ДКА, НКА и РВ.png

Задача

Преобразовать автомат в регулярное выражение.

3 4(0) — Задача (КА в РВ).png

Последовательно процесс удаления изображён на следующих изображениях:

Процесс удаления вершин лучше всегда начинать с вершин, через которые проходит меньше всего путей

Получившееся выражение можно упростить:\[ (ab^*\Sigma a+a)^*ab^*\Sigma+(ab^*\Sigma a+a)^*=(ab^*\Sigma a+a)^*(ab^*\Sigma + \varepsilon)=(ab^*\Sigma a+a)^*(ab^*\Sigma)? \] Кроме того, возможно и упрощение в первой скобке выражения \((ab^*\Sigma a+a)=a(b^*\Sigma a)?=(ab^*\Sigma)?a\).

Лемма о разрастании

Формулировка

Если \(L\) — регулярный язык, то для него \(\exists p \in\mathbb{N}\:\: \forall s \in L: \lvert s \rvert \geqslant p \Rightarrow s=xyz\) (слово \(s\) может быть разбито на три части) т. о., что

  • \(\forall i \in \mathbb{N_0} \:\: xy^iz\in L\)
  • \(\lvert y \rvert > 0 \)
  • \(\lvert xy \rvert \leqslant p \)

Доказательство

Зафиксируем некий регулярный язык, описываемый ДКА (по определению). Тогда за число \(p\) возьмём число состояний этого ДКА, взятое на единицу больше \((p=\lvert Q\rvert+1)\).

Возьмём \(\forall s \in L: \lvert s \rvert \geqslant p \).

Теперь скажем, что \(s=s_0s_1\ldots s_n\), где \(n=\lvert s \rvert\)

Опишем последовательность состояний \(r=r_0r_1\ldots r_{n+1}\), где \(\lvert r \rvert = n + 1 \geqslant p+1\).

Возьмём из \(r\) первые \(p+1\) состояний и среди них по принципу Дирихле хотя бы одно встретится дважды. Т. е. у нас есть такая последовательность:\[\underbrace{r_0r_1\ldots r}_{x}\underbrace{_j\ldots r}_{y}\underbrace{_l\ldots r_{n+1}}_{z}\;\;\;\: r_j=r_l \:\;\;\; j \ne l\]

Проходя по этой последовательности, получаем слова \( x = s_0\ldots s_{j-1}, \: y = s_j \ldots s_{l-1}, \: z = s_l \ldots s_n \), причём \(\lvert y \rvert > 0\).

3 5 — Рисунок к лемме.png

Из такого построения видно, что \(y\) в слове может быть сколько угодно, т. е. \(xz\in L, \;xyz\in L, \; xyyz\in L, \; xyyyz\in L\) и т. д. Поскольку \(z\) нас всегда приводит в конечную вершину, а \(x\) всегда приведёт из начальной вершины в вершину \(r_j=r_l\), в которой есть «петля» \(y\).

Осталось показать, что \(\lvert xy \rvert \leqslant p \). Мы уже взяли \(p+1\) состояния, в которых обязательно два одинаковых \((r_j=r_l\in r_0 \ldots r_p)\) и \(j<l<p+1\). Отсюда следует, что \(\lvert xy \rvert \leqslant p \).