LoginSignup
1
0

More than 1 year has passed since last update.

文脈自由文法からε動作を削除する感覚的説明

Last updated at Posted at 2021-08-01

オートマトンに関する教科書の数式的な説明がわかりにくいと感じたので、感覚的な自分なりの説明を載せます。情報系の学生向けの記事です。

空白化記号$N_\epsilon$は求まってるとします。

1.そのままパスできる生成規則をパスさせる

まず、生成規則の右側で空白化記号をないものはそのまま新しい生成規則のリストに追加。

2.空白記号を右側に含む生成規則は場合によっては複数に分岐させる

空白記号が生成規則の右側にあるものは、変更の可能性があるので注目。

そのような特定の生成規則に着目する。
その生成規則の右側にある空白化記号(1つの場合もあれば、複数の場合もある)
その生成規則の右側の空白化記号を削除したものを新しい規則のリストに追加する。
例えば、右側に空白化記号$B,C\in N_{\epsilon}$があった場合

4通り:
何も消さない
Bのみを消す
Cのみを消す
BもCも消す

これらの処理をした各4つの生成規則を、新しい規則のリストに追加する。
もし空白化記号をいくつか消した後に、右辺が$\epsilon$になった場合は、それは新しいリストには加えず、次の消し方の候補にすすむ。

空白化記号を右辺に含むような生成規則について、全てに同様の作業をする

3.Sがもし空白化記号の場合の例外処理 (Optional)

まれに$S\in N_\epsilon$の場合は非終端記号の集合$N$と$S$を新しいものにしなければならない。アンパンマンの汚れた顔を、新しい顔に付け替えるのと同じ感覚です。

形式的に$S'\rightarrow \epsilon, S'\rightarrow S$を生成規則に追加します。

これは$\epsilon$なしの定義で、$\epsilon$が生成規則にあったとしても開始記号だけだよ、という条件に合わせるための作業です。

これに伴い、$N$に$S'$に追加した新しい非終端記号の$N'$を回答の最後に書いておきましょう。

これでひと段落。

参考文献

オートマトン・言語理論 森北出版

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0