ТМВ-2019-Семинар-11.02.2020

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

Детерминированные конечные автоматы (ДКА)

Рис. 1 — ДКА: наличие подстроки \(aa\)

Как уже известно, детерминированный конечный автомат (ДКА) характеризуется тем, что из каждого его состояния существуют единственные (!) переходы в другие состояния по каждой букве из алфавита \(\Sigma\). На прошлом семинаре мы ознакомились с графическим способом задания таких автоматов (рис. 1). Однако существует ещё и другой способ описания автомата c помощью матрицы переходов.

Матрица переходов для конечного автомата

В столбцах у нас все элементы алфавита \(\Sigma\), а в строках, соответственно, допустимые состояния из множества \(Q\). Таким образом, на пересечении \((i, j)\) элемента такой таблицы будет состояние \(q_k\colon q_i\xrightarrow{w_j}q_k, \text{где }q_i\in Q, w_j\in\Sigma\). Начальное состояние отмечено знаком \(\to\), а конечные (терминальные) – \(*\). Следующая таблица описывает автомат, изображённый на рис. 1:\[ \begin{array}{r|cc} & a & b \\ \hline \to q_0 & q_1 & q_0 \\ q_1 & q_2 & q_0 \\ *\,q_2 & q_2 & q_2 \\ \end{array} \]

Регулярные языки. Дополнение к языку

Регулярный язык — язык, для которого можно построить детерминированный конечный автомат. Таким образом, автомат на рис. 1 описывает регулярный язык \(L\), определяющий вхождение подстроки \(aa\) в рассматриваемом слове. Рассмотрим теперь язык \(\overline{L}\), который назовём дополнением к регулярному языку \(L\).

\[\overline{L}=\{\omega\in\Sigma_L^*\mid\omega\notin L\}\]

То есть, в язык \(\overline{L}\) входят все слова, которые не входят в регулярный язык \(L\). Если рассматривать язык автомата на рис. 1, то дополнением к нему будет язык, который определяет слова, в которых нет двух идущих подряд букв \(a\). Напрашивается вопрос: является ли само дополнение к регулярному языку регулярным языком?. Попробуем построить ДКА для такого языка. Для построения ДКА для \(\overline{L}\) достаточно все конечные (терминальные) состояния объявить неконечными, а все остальные наоборот — конечными (т. е. инвертировать состояния): \[T_{\overline{L}} = Q \setminus T_L\] Соответственно, если на автомате (рис. 1) состояния \(\{q_0,q_1\}\in T\), а \(\{q_2\}\notin T\), то тогда такой автомат описывает \(\overline{L}\).

Таким образом, можно сделать вывод, что дополнение к регулярному языку — регулярный язык.

Разбор задачи для самостоятельного разбора из семинара 1

Попробуем построить такой автомат по индукции. Построим автоматы, определяющие слова, у которых \(1\) на последнем, предпоследнем и предпредпоследнем местах:

Соответственно, можно найти закономерности, благодаря которым возможно дальнейшее построение автоматов, для которых \(1\) на четвёртом, пятом, ..., десятом местах с конца. (Самостоятельно построить автомат для случая, когда \(1\) на десятом месте с конца).

На самом деле такое громоздкое рутинное задание было дано неслучайно. Рассмотрим теперь новый вид автоматов, который поможет решать нам такие задачки несколько проще.

Недетерминированные конечные автоматы (НКА)

Рис. 2 — HКА

В ДКА существует единственная последовательность действий, которая определяет, является ли слово частью языка (за счёт единственности переходов между состояниями). У нас уже были примеры автоматов, которые являются недетерминированными (1 1 — Примеры автоматов.jpg: по центру, справа). Рассмотрим автомат на рис. 2 и попробуем пройти по этому автомату словом \(01011\). По \(0\) у нас есть только один путь, поэтому проблем не возникает: \[q_0 \xrightarrow{0} q_0\] По \(1\) мы уже не знаем куда перейти, соответственно, пройдём по всем возможным путям. Видим, что наше слово \(01011\) может как попасть в конечное (терминальное) состояние, так и не попасть. Попробуем описать формально все возможные переходы, рассматривая уже в случае нескольких возможных путей комбинации состояний: \[ q_0 \xrightarrow{0} q_0 \\ q_0 \xrightarrow{1} \{q_0,q_1\} \\ \{q_0,q_1\} \xrightarrow{0} \{q_0,q_3\} \\ \{q_0,q_3\} \xrightarrow{1} \{q_0,q_1,q_3\} \\ \{q_0,q_1,q_3\} \xrightarrow{1} \{q_0,q_1,\color{red}{q_2},q_3\} \\ \] В НКА, если хоть один путь ведёт к конечному состоянию, то слово является частью языка. Таким образом, т. к. мы встретили после обработки слова конечное состояние \(q_2\), делаем вывод\(:\) \(01011\) является частью языка.

Теперь построить автомат, для которого \(1\) третья с конца будет проще:

2 6 — НКА(2).png

Автомат с \(\varepsilon(\lambda)\)-переходами

Рис. 3 — HКА с \(\varepsilon(\lambda)\)-переходами

Зачем они нужны? Если автомат находится в состоянии, из которого доступен \(\varepsilon(\lambda)\)-переход, он может его сделать за то же время, что он попадает в это состояние, т. е. в начальный момент времени в НКА, когда строчка ещё начинает вводиться, автомат сразу может совершить такой переход и оказаться в одном из двух состояний.

Рассмотрим автомат (рис. 3) и cлово \(baabb\). Начать с буквы \(b\) мы можем, совершив \(\varepsilon(\lambda)\)-переход. То есть наше слово определится автоматом следующей цепочкой\(:\) \(\varepsilon b\varepsilon aa\varepsilon bb\).

На самом деле, по НКА проще понять какую строчку он принимает, чем ту, которую он не принимает. Здесь работает такой подход: интуитивно для конкретной задачи определить возможные пути для конечного слова и построить его недетерминированным образом, а затем уже его можно детерминировать. Попробуем это сделать для следующего языка: \[L=\{\omega\in\{0,1\}^*\mid\omega\text{ заканчивается на }010\text{ или }101\}\] НКА для такого языка будет следующим:

2 7 — НКА (заканч. на 010 или 101).png

Переход от НКА к ДКА

Рассмотрим следующий язык\[L=\{\omega\in\{a,b,c\}^*\mid\omega\text{ не содержит либо }a\text{, либо }b\text{, либо }c\}\] Например, простейшими словами, в которых нет буквы \(a\) будут \(\varepsilon(\lambda), b, c\) (аналогично для других букв алфавита). Соответственно, НКА для данного языка будет следующим:

2 8 — НКА (не содержит либо a, либо b, либо c).png

Из НКА можно получить ДКА следующим образом. Составим матрицу переходов для НКА, изображённого выше.

\[ \begin{array}{r|ccc} & a & b & c \\ \hline \to *\, \{q_1,q_2,q_3,q_4\} & \{q_3,q_4\} & \{q_2,q_4\} & \{q_2,q_3\} \\ *\, \{q_3,q_4\} & \{q_3,q_4\} & q_4 & q_3 \\ *\, \{q_2,q_4\} & q_4 & \{q_2,q_4\} & q_2 \\ *\, \{q_2,q_3\} & q_3 & q_2 & \{q_2,q_3\} \\ *\, q_2 & \emptyset & q_2 & q_2 \\ *\, q_3 & q_3 & \emptyset & q_3 \\ *\, q_4 & q_4 & q_4 & \emptyset \\ \emptyset & \emptyset & \emptyset & \emptyset \\ \end{array} \]

На основе данной матрицы переходов строим следующий ДКА:

2 9 — ДКА из НКА (не содержит либо a, либо b, либо c).png

Такой метод построения ДКА называется методом построения подмножеств. Главные особенности:

  • каждое состояние ДКА — множество состояний НКА (возможно и пустое множество);
  • начальным состоянием ДКА будет множество, состоящее из начального состояния НКА и всех состояний, доступных \(\varepsilon(\lambda)\)-переходами;
  • конечными состояниями ДКА будут те множества состояний НКА, которые содержат хотя бы одно конечное состояние НКА.

Следствие

Так как существует процедура, которая преобразует НКА в ДКА, то можем утверждать следующее:

Язык, для которого можно построить недетерминированный конечный автомат (НКА), также является регулярным языком

Задача 1

Преобразовать следующий НКА в ДКА.

2 10 — НКА (задача 1).png

Строим матрицу переходов для данного автомата: \[ \begin{array}{r|cc} & a & b \\ \hline \to *\,\{q_0\} & \{q_0,q_1\} & \{q_1\} \\ *\, \{q_0,q_1\} & \{q_0,q_1\} & \{q_0,q_1\} \\ \{q_1\} & \emptyset & \{q_0\} \\ \end{array} \] На основе данной таблицы строим ДКА:

2 11 — ДКА (задача 1).png

Задача 2

Преобразовать следующий НКА в ДКА.

2 13 — НКА (задача 2).png

Строим матрицу переходов для данного автомата: \begin{array}{r|cc} & a & b \\ \hline \to \{q_0\} & \{q_0,q_1\} & \{q_0\} \\ \{q_0,q_1\} & \{q_0,q_1\} & \{q_0,q_2\} \\ \{q_0,q_2\} & \{q_0,q_1,q_3\} & \{q_0\} \\ *\,\{q_0,q_1,q_3\} & \{q_0,q_1\} & \{q_0,q_2\} \\ \end{array} На основе данной таблицы строим ДКА:

2 14 — ДКА из НКА (задача 2)(edit).png

Операции над регулярными языками

Рис. 4 — Операции над языками

Будем рассматривать два регулярных языка \(L_1, L_2\), для которых построены автоматы (рис. 4). Определим следующие операции над ними:

Объединение

\[L_1 + L_2 = \{\omega\mid\omega\in L_1 \vee \omega\in L_2\}\]

Для построения НКА объединения автоматов \(L_1, L_2\) достаточно определить новое начальное состояние и организовать \(\varepsilon(\lambda)\)-переходы в начальные вершины этих автоматов (рис. 4).

Конкатенация

\[L_1L_2 = \{\omega_1\omega_2\mid\omega\in L_1,\omega\in L_2\}\]

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

Итерация (операция Клини)

\[L^*=\{\varepsilon(\lambda)\} + L + LL\, + ... +\, \underbrace{LL...L}_{n}\, + ...\]

Для построения НКА для итерации необходимо определить новое начальное состояние, которое будет ещё и конечным (для определения пустого слова как часть языка), и из всех конечных состояний организовать \(\varepsilon(\lambda)\)-переход в прежнее начальное состояние автомата (рис. 4).

Задача для самостоятельного разбора

Преобразовать следующий НКА в ДКА.

2 15 — Домашняя задача (из НКА в ДКА)(1).png