正規文法

正規文法(Regular Grammar)の定義

形式文法 $G=(N,T,P,S)$ における生成規則 $P$ が以下で表されるとき,その形式文法 $G$ は正規文法といいます.\[S \to \varepsilon\tag{1}\]\[A \to \alpha\tag{2}\]\[A \to \alpha B\tag{3}\]ここで,終端記号の集合 $T$(Terminal symbol) ,非終端記号の集合 $N$(Non-terminal symbol),生成規則の集合 $P$(Production rule),開始記号 $S$(Start symbol) であり,\[\forall A\forall B \in N\]\[\forall \alpha \in T\]です.

生成規則と状態遷移関数

正規文法の生成規則を以下のように有限オートマトンの状態遷移関数に対応させると,正規文法は有限オートマトンに変換することができます.

生成規則状態遷移関数
$S \to \varepsilon$$\delta(S,\varepsilon)=q_{f}$
$A \to \alpha$$\delta(A,\alpha)=q_{f}$
$A \to \alpha B$$\delta(A,\alpha)=B$

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 形式文法と有限オートマトン 文と言語と文法 ゾゾウスキ導分(Brzozowski derivative) 導出(derive) 形式文法