形式文法と有限オートマトン

有限オートマトン

$Q$ を状態の空ではない有限集合，$\Sigma$ を入力記号の集合（$a \in \Sigma$），$\delta$ を状態遷移関数，$q_{0} \in Q$ を初期状態，$F \subset Q$ は受理状態の集合とすると，有限オートマトンは，\[M = (Q,\Sigma,\delta,q_{0},F)\]と表されます．

形式文法

形式言語の文法は，終端記号の集合 $T$（Terminal symbol） ，非終端記号の集合 $N$（Non-terminal symbol），生成規則の集合 $P$（Production rule），開始記号 $S$（Start symbol） によって，\[G=(N,T,P,S)\]と表されます．

形式文法と有限オートマトン

有限オートマトン形式文法
初期状態 $q_{0}$開始記号 $S$
受理記号列 $F \subset Q$導出文 $\mathcal{L}(G)$
状態生成途中の記号列
状態遷移関数 $\delta$生成規則 $P$


Mathematics is the language with which God has written the universe.