導出(derive)

形式文法 $G=(N,T,P,S)$ において,非終端記号 $A$ からなる記号列 $xA$ に対して,$P$ に含まれる生成規則の1つが,\[A \to aB\ (A,B \in N\ ,\ a \in \Sigma)\]であるとき,この生成規則によって,文法 $G$ は記号列 $xA$ から記号列 $xaB$ を直接導出するといいます.

そして,\[xA \xrightarrow[G]{}xaB\]と表します.

また,記号列 $xA$ から直接導出を繰り返すことによって記号列 $xaB$ が得られる時,文法 $G$ は記号列 $xA$ から記号列 $xaB$ を導出するといいます.\[xA \xrightarrow[G]{} x_{1}A \xrightarrow[G]{} \cdots \xrightarrow[G]{} xaB\]上記の導出は,\[xA \overset{G}{\Rightarrow} xaB\]と表されます.

Vita brevis, ars longa. Omnia vincit Amor.





















濃度 形式文法 真偽値表/真理値表 有限オートマトンの多様体 正規言語(regular lamguage) セルオートマトン