正規言語の並列定義
定義1. 正規言語の定義
\begin{align} Lは正規言語である\overset{\mathrm{def}}{\iff}Lが正規文法によって生成される \end{align}
定理1. 正規言語の並列定義
\begin{align} &任意のL\in\Sigma^*について、以下は全て等価である.\\[5pt] &Lは正規言語である(Lが正規文法によって生成される).\tag{1.1}\\ &Lを受理するDFA(決定性有限オートマトン)が存在する.\tag{1.2}\\ &Lを受理するNFA(非決定性有限オートマトン)が存在する.\tag{1.3}\\ &Lを受理する\epsilon\mathrm{-}動作付きNFAが存在する.\tag{1.4}\\ \end{align}
(1.2)を正規言語の定義としている書籍も多いです。
定理1の証明
補題1. DFAとNFAの言語受理能力の同等性
\begin{align} \forall L\in\Sigma^* (Lを受理する\mathrm{DFA}が存在する\Longleftrightarrow Lを受理する\mathrm{NFA}が存在する) \tag{2} \end{align}
補題2. ε-動作付きNFAからε-動作を除去
\begin{align} &\forall L\in\Sigma^*\\ &(Lを受理する\mathrm{NFA}が存在する \Longleftrightarrow Lを受理する\epsilon\mathrm{-}動作付き\mathrm{NFA}が存在する) \tag{3} \end{align}
定理1の証明
\begin{align} &(2),(3)より、(1.2)\Leftrightarrow (1.3)\Leftrightarrow (1.4) は示された。\\ &以下、(1.1)\Leftrightarrow (1.4)を示す。\\[5pt] &G=(N,T,\sigma,P)\in\mathcal{REG} \ \ (P=\{\alpha\rightarrow\beta\ |\ \alpha\in N,\beta\in T^* \cup T^*N\})\ および\\ &\epsilon\mathrm{-}動作付き\mathrm{NFA} \ M=(Q,\Sigma,\delta,q_0,F) \ (\delta :Q\times(\Sigma\cup\{\lambda\})\to 2^Q)\\ &について、以下のような対応を考える。\\ &(ただし\ A,B\in N,\ a\in T,\ q,r\in(Q\setminus F),\ f\in F) \\[5pt] \end{align} \begin{align} &A\rightarrow aB&&\longleftrightarrow&&\delta(q,a)=r\\ &A\rightarrow a&&\longleftrightarrow&&\delta(q,a)=f\\ &A\rightarrow\lambda&&\longleftrightarrow &&\delta(q,\lambda)=f\\[5pt] \end{align} \begin{align} &このときL(G)=L(M)が成り立ち、よって題意は示された。 \end{align}