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

有限オートマトン

$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）形式文法真偽値表/真理値表