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

有限オートマトン

$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.

二項分布とポアソン分布の関係 文と言語と文法 ゾゾウスキ導分（Brzozowski derivative） 導出（derive） 形式文法 真偽値表/真理値表