日付や時間を表す文字列を受理するオートマトン①

日付や時間に関する型も用意して、オートマトンでチェックしたい。受理したい形式は以下。

  • yyyy/mm/dd hh:MM:ss.fff
  • yyyy/mm/dd hh:MM:ss
  • yyyy/mm/dd hh:MM
  • yyyy/mm/dd hh
  • hh:MM:ss.fff
  • hh:MM:ss
  • hh:MM
  • MM:ss.fff
  • MM:ss
  • ss.fff

時刻部分はAM/PM表記も許したいな。例えば"01:23 AM"や"01:23:45 PM"とか。
このままだと、hh:MMとMM:ssを区別できないし、ss.fffと実数も区別できない。

整数、実数の時と同じようにDFAC#で実装したい。

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

先日εNFAをNFAに変換した。
今度はこのNFAをDFAに変換したい。これをやるのが「部分集合構成法」というものらしい。以下にDFAの状態遷移表を作っていく。
NFAの初期状態はS_{0}のみなので、初期状態の集合は\{S_{0}\}となる。そして、初期状態の集合から遷移する可能性のある状態をまとめて遷移先の状態と考える。こんな感じ。

状態 X Y Z .
\{S_{0}\} \{S_{1}\} \{S_{2},S_{3},S_{5},S_{13},S_{19}\} \{S_{9}\}
続きを読む

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

自分の理解力の無さから、参考にしようとしていたサイトの説明では行き詰ってしまった。なのでオートマトンの教科書を読んでみた。
ε動作ありのNFAから、ε動作なしのNFAへの変換のやり方が書いてあったので、やってみた。
まず\epsilon-Cl(S_{i})(ε閉包というらしい)というものを定義してみる。これは状態S_{i}からε動作だけで到達できる状態の集合(ただしS_{i}自身の含む)を表す。

続きを読む

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

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

  • RS

f:id:yagiey:20181002220915p:plain

  • R|S

f:id:yagiey:20181002220913p:plain

  • R*

f:id:yagiey:20181002220910p:plain

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

^[-+]?([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*)?$

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

続きを読む