実数を表す文字列を受理するオートマトン①

前回のつづき。「正規表現とNFA・DFA」を参考に、実数の正規表現を元に状態遷移図を描いて、C#で実装してみたい。
RとSを正規表現とすると、RSとR|SとR*を受理するオートマトン（ただし、ε遷移あり）は次のように表現できるらしい。

• RS

• R|S

• R*

「整数を表す文字列を受理するオートマトン - チキン煮込みチーズミックス４辛」で、実数を表す文字列の正規表現は

^[-+]?([0-9]+(\.[0-9]*)?|\.[0-9]+)([eE][-+]?[0-9]+)?$

って書いたけど、上記3つを使って考えるために、次のように書き換えよう。

^[-+]?([0-9][0-9]*(\.[0-9]*)?|\.[0-9][0-9]*)([eE][-+]?[0-9][0-9]*)?$

さらに、簡単化のために[-+]と[0-9]と[eE]をそれぞれX、Y、Zとおいて、

^X?(YY*(\.Y*)?|\.YY*)(ZX?YY*)?$

としてみる。とりあえず、状態遷移図はε遷移を含んだ形で作っていく。上記の正規表現を小分けにして考えて、最後に合体させてから、ε遷移を除去していくことを考える。

X?

Xがあっても無くてもいいってことなので

YY*

YとY*を繋げたものなので

(\.Y*)?

\.とY*を繋げたもの全体が、あっても無くてもよいので

(YY*(\.Y*)?|\.YY*)

前二つを参考にして

(ZX?YY*)?

指数部分。ZX?YY*があっても無くてもいいので

全部合体すると

これをもとに、ε遷移を除去していくことにする。
（つづく）