正規言語の閉包性

定理1. 正規言語の閉包性

任意の \(L,L_1,L_2\in\mathcal{REG}\) について

\begin{align} &\overline{L}\ (=\Sigma^*\setminus L)\in\mathcal{REG}\tag{1.1}\\ &L_1\cup L_2\in\mathcal{REG}\tag{1.2}\\ &L_1\cap L_2\in\mathcal{REG}\tag{1.3}\\ \end{align}

定理1の証明

補題1. 正規言語の並列定義

\begin{align} &\forall L\in\Sigma^*(L\in\mathcal{REG}\Longleftrightarrow Lを受理するDFAが存在する)\tag{2.1}\\ &\forall L\in\Sigma^*(L\in\mathcal{REG}\Longleftrightarrow Lを受理する\epsilon\mathrm{-}動作付きNFAが存在する)\tag{2.2} \end{align}

(1.1)の証明

\begin{align} &(2.1)より、任意のL\in\mathcal{REG}について\\ &Lを受理する\mathrm{DFA}\ M=(Q,\Sigma,\delta,q_0,F)が存在する。\\ &ここで\mathrm{DFA}\ M'=(Q,\Sigma,\delta,q_0,(Q\setminus F))は\overline Lを受理する。\\ &よって(2.1)より、\overline{L}\in\mathcal{REG} \end{align}

(1.2)の証明

\begin{align} &(2.2)より、任意のL_1,L_2\in\mathcal{REG}について L_1,L_2を受理する\\ &\epsilon\mathrm{-}動作付き\mathrm{NFA}\\ &M_1=(Q_1,\Sigma_1,\delta_1,q_{(1)0},F_1),\\ &M_2=(Q_2,\Sigma_2,\delta_2,q_{(2)0},F_2)が存在する。\\ \end{align} \begin{align} ここで&&Q&=Q_1\cup Q_2\cup\{q_0\}\\ &&\Sigma&=\Sigma_1\cup\Sigma_2\\ &&\delta&=\delta_1\cup\delta_2\cup \{q_0\rightarrow q_{(1)0}, \ q_0\rightarrow q_{(2)0}\}\\ &&F&=F_1\cup F_2\ としたときの\\ \end{align} \begin{align} &\epsilon\mathrm{-}動作付き\mathrm{NFA} \ M=(Q,\Sigma,\delta,q_{0},F)はL_1\cup L_2を受理する。\\ &よって(2.2)より、L_1\cup L_2\in\mathcal{REG} \end{align}