Недетерминированный конечный автомат

НКА формально представляется как 5-кортеж ${\displaystyle (Q,\Sigma ,\Delta ,q_{0},F)}$, состоящий из:

• конечного множества состояний ${\displaystyle Q}$.
• конечного множества входных символов ${\displaystyle \Sigma }$.
• функции переходов ${\displaystyle \Delta }$ : ${\displaystyle Q\times \Sigma \rightarrow P(Q)}$.
• начального состояния ${\displaystyle q_{0}\in Q}$.
• множества состояний ${\displaystyle F}$ распознаваемых как конечные состояния ${\displaystyle F\subseteq Q}$.

Здесь ${\displaystyle P(Q)}$ означает степень множества ${\displaystyle Q}$.

Если дан НКА ${\displaystyle M=(Q,\Sigma ,\Delta ,q_{0},F)}$, он распознаёт язык, который обозначается как ${\displaystyle L(M)}$ и определяется как множество всех строк над алфавитом ${\displaystyle \Sigma }$, принимаемых автоматом ${\displaystyle M}$.

В общих чертах согласно неформальным объяснениям выше, существует несколько эквивалентных формальных определений строки ${\displaystyle w=a_{1}a_{2}...a_{n}}$, принимаемых автоматом ${\displaystyle M}$:

• ${\displaystyle w}$ принимается, если существует последовательность состояний ${\displaystyle r_{0},r_{1},...,r_{n}}$ в ${\displaystyle Q}$ такая, что
  1. ${\displaystyle r_{0}=q_{0}}$
  2. ${\displaystyle r_{i+1}\in \Delta (r_{i},a_{i+1})}$, для ${\displaystyle i=0,\ldots ,n-1}$
  3. ${\displaystyle r_{n}\in F}$.

Словами. Первое условие гласит, что машина начинает работу из состояния ${\displaystyle q_{0}}$. Второе условие гласит, что для каждого символа строки ${\displaystyle w}$ машина переходит из состояния в состояние согласно функции переходов ${\displaystyle \Delta }$. Последнее условие гласит, что машина принимает строку ${\displaystyle w}$, если входная строка ${\displaystyle w}$ приводит машину к завершению в конечном состоянии. Чтобы строка ${\displaystyle w}$ была принята автоматом ${\displaystyle M}$, не требуется, чтобы любая последовательность состояний завершается в конечном состоянии, достаточно, чтобы в такое состояние приводила одна последовательность. В противном случае, то есть, если невозможно перейти из ${\displaystyle q_{0}}$ в состояние из ${\displaystyle F}$, следуя ${\displaystyle w}$, говорят, что автомат отвергает строку. Множество строк, которые автомат ${\displaystyle M}$ принимает, является языком, распознаваемым автоматом ${\displaystyle M}$, и этот язык обозначается как ${\displaystyle L(M)}$[9][10].

• Альтернативно, ${\displaystyle w}$ принимается, если ${\displaystyle \Delta ^{*}(q_{0},w)\cap F\not =\emptyset }$, где ${\displaystyle \Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)}$ определяется рекурсивно:
  1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\}}$, где ${\displaystyle \epsilon }$ является пустой строкой
  2. ${\displaystyle \Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)}$ для любого ${\displaystyle x\in \Sigma ^{*},a\in \Sigma }$.

Словами, ${\displaystyle \Delta ^{*}(r,x)}$ является множеством всех состояний, достижимых из состояния ${\displaystyle r}$ при получении строки ${\displaystyle x}$. Строка ${\displaystyle w}$ принимается, если некоторое конечное состояние из ${\displaystyle F}$ может быть достигнуто из начального состояния ${\displaystyle q_{0}}$ для входной строки ${\displaystyle w}$[11][12].

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

НКА-ε формально представляется 5-кортежем, ${\displaystyle (Q,\Sigma ,\Delta ,q_{0},F)}$, который состоит из:

• конечного множества состояний ${\displaystyle Q}$
• конечного множества входных символов, называемого алфавитом ${\displaystyle \Sigma }$
• функции переходов ${\displaystyle \Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)}$
• начального (или стартового) состояния ${\displaystyle q_{0}\in Q}$
• набора состояний ${\displaystyle F}$, считающихся допустимыми (или конечными) состояниями ${\displaystyle F\subseteq Q}$.

Здесь ${\displaystyle P(Q)}$ означает степень множества ${\displaystyle Q}$, а ε означает пустую строку.

Для состояния ${\displaystyle q\in Q}$ пусть ${\displaystyle E(q)}$ означает множество состояний, достижимых из ${\displaystyle q}$ следующими ε-переходами в функции переходов ${\displaystyle \Delta }$, а именно, ${\displaystyle p\in E(q)}$ если существует последовательность состояний ${\displaystyle q_{1},...,q_{k}}$ таких, что:

• ${\displaystyle q_{1}=q}$,
• ${\displaystyle q_{i+1}\in \Delta (q_{i},\epsilon )}$ для любых ${\displaystyle 1\leqslant i<k}$
• ${\displaystyle q_{k}=p}$.

Множество ${\displaystyle E(q)}$ известно как ε-замыкание состояния ${\displaystyle q}$.

ε-замыкание определяется также для множества состояний. ε-замыкание множества состояний, ${\displaystyle P}$, НК-автомата определяется как множество состояний, достижимых из элементов множества ${\displaystyle P}$ по ε-переходам. Формально, для ${\displaystyle P\subseteq QE(P)=\cup _{q\in P}E(q)}$.

Пусть ${\displaystyle w=a_{1}a_{2}...a_{n}}$ будет строкой над алфавитом ${\displaystyle \Sigma }$. Автомат ${\displaystyle M}$ принимает строку ${\displaystyle w}$, если существует последовательность состояний ${\displaystyle r_{0},r_{1},...,r_{n}}$ в ${\displaystyle Q}$ со следующими условиями:

1. ${\displaystyle r_{0}\in E(q_{0})}$
2. ${\displaystyle r_{i+1}\in E(r')}$, где ${\displaystyle r'\in \Delta (r_{i},a_{i+1})}$ для любого ${\displaystyle i=0,...,n-1}$
3. ${\displaystyle r_{n}\in F}$.

Словами. Первое условие говорит, что машина начинает с состояния, которое достижимо из состояния ${\displaystyle q_{0}}$ по ε-переходам. Второе условие говорит, что после чтения ${\displaystyle a_{i}}$ машина выбирает переход ${\displaystyle \Delta }$ из ${\displaystyle r_{i}}$ в ${\displaystyle r'}$, а затем осуществляет любое число ε-переходов согласно ${\displaystyle \Delta }$ для перехода из ${\displaystyle r'}$ в ${\displaystyle r_{i+1}}$. Последнее условие говорит, что машина принимает ${\displaystyle w}$, если последний входной символ приводит к переходу машины в одно из принимаемых состояний. В противном случае говорят, что автомат отвергает строку. Множество строк, которые ${\displaystyle M}$ принимает, является языком, который распознаёт автомат ${\displaystyle M}$, и этот язык обозначается как ${\displaystyle L(M)}$.

Диаграмма состояний автомата M

Пусть ${\displaystyle M}$ будет НКА-ε с двоичным алфавитом, который определяет, если входная строка содержит чётное число нулей или чётное число единиц. Заметим, что 0 случаев является чётным числом.

В формальных обозначениях, пусть ${\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0},\{S_{1},S_{3}\})}$, где отношение переходов ${\displaystyle \Delta }$ может быть определено такой таблицей переходов состояний:

${\displaystyle M}$ можно рассматривать как объединение двух ДКА — один с состояниями ${\displaystyle \{S_{1},S_{2}\}}$, а другой с состояниями ${\displaystyle \{S_{3},S_{4}\}}$. Язык ${\displaystyle M}$ можно описать как регулярный язык, заданный регулярным выражением (1*(01*01*)*) ∪ (0*(10*10*)*). Мы определяем ${\displaystyle M}$ с помощью ε-переходов, но ${\displaystyle M}$ можно определить и без них.

Чтобы показать, что НКА-ε эквивалентен НКА, сначала обратим внимание на то, что НКА является частным случаем НКА-ε, остаётся показать, что для любого НКА-ε существует эквивалентный НКА.

Пусть ${\displaystyle A=(Q,\Sigma ,\Delta ,q_{0},F)}$ будет НКА-ε. НКА ${\displaystyle A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)}$ эквивалентен ${\displaystyle A}$, где для любого ${\displaystyle a\in \Sigma }$ и ${\displaystyle q\in Q}$ ${\displaystyle \Delta '(q,a)=E(\Delta (q,a))}$.

Тогда НКА-ε эквивалентен НКА. Поскольку НКА эквивалентен ДКА, НКА-ε также эквивалентен ДКА.