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

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

状態	X	Y	Z	.

次は、、、からの遷移を考えるとこんな感じ。
（2022/1/29追記）以降の内容には誤りがありました。訂正日記を後日書きます！

状態	X	Y	Z	.

この要領で状態遷移表を完成させるとこんな感じ。

状態	X	Y	Z	.

見やすくするために、集合で表現していた状態を新しい記号で置き換えるとこんな感じ。受理状態の集合は、元のNFAの受理状態であるを含んでいるとなる。

状態	X	Y	Z	.

（2022/1/29追記）訂正日記書きました。
yagiey.hatenablog.com

実装してみた

入力Xは[-+]、Yは[0-9]、Zは[eE]であることを思い出して、実装してみた。

class FloatChecker : Checker
{
  enum FloatParsingState
  {
    Error,
    State00,
    State01,
    State02,
    State03,
    State04,
    State05,
    State06,
    State07,
    State08,
    State09,
    State10,
    State11,
  }

  FloatParsingState _state;

  public FloatChecker()
  {
    Reset();
  }

  public void Reset()
  {
    _state = FloatParsingState.State00;
  }

  void Transition(char ch, FloatParsingState whenX, FloatParsingState whenY, FloatParsingState whenZ, FloatParsingState whenDot)
  {
    if (ch == '-' || ch == '+')
    {
      _state = whenX;
    }
    else if (char.IsDigit(ch))
    {
      _state = whenY;
    }
    else if (ch == 'e' || ch == 'E')
    {
      _state = whenZ;
    }
    else if (ch == '.')
    {
      _state = whenDot;
    }
    else
    {
      _state = FloatParsingState.Error;
    }
  }

  public void Next(char ch)
  {
    switch (_state)
    {
      case FloatParsingState.State00:
        Transition(
          ch,
          FloatParsingState.State01,
          FloatParsingState.State02,
          FloatParsingState.Error,
          FloatParsingState.State03);
        break;
      case FloatParsingState.State01:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State02,
          FloatParsingState.Error,
          FloatParsingState.State03);
        break;
      case FloatParsingState.State02:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State02,
          FloatParsingState.State04,
          FloatParsingState.State05);
        break;
      case FloatParsingState.State03:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State06,
          FloatParsingState.Error,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State04:
        Transition(
          ch,
          FloatParsingState.State07,
          FloatParsingState.State08,
          FloatParsingState.State08,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State05:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State09,
          FloatParsingState.State04,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State06:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State10,
          FloatParsingState.State04,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State07:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State08,
          FloatParsingState.Error,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State08:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State11,
          FloatParsingState.Error,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State09:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State09,
          FloatParsingState.State04,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State10:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State10,
          FloatParsingState.State04,
          FloatParsingState.Error);
        break;
      case FloatParsingState.State11:
        Transition(
          ch,
          FloatParsingState.Error,
          FloatParsingState.State11,
          FloatParsingState.Error,
          FloatParsingState.Error);
        break;
    }
  }

  public bool IsAcceptable()
  {
    return
      _state == FloatParsingState.State02 ||
      _state == FloatParsingState.State05 ||
      _state == FloatParsingState.State06 ||
      _state == FloatParsingState.State08 ||
      _state == FloatParsingState.State09 ||
      _state == FloatParsingState.State10 ||
      _state == FloatParsingState.State11;
  }

  public bool IsError()
  {
    return _state == FloatParsingState.Error;
  }
}

こうやって構成した状態遷移図は、無駄がある場合があるらしい。その場合は遷移図を無駄を省くアルゴリズムで対処可能らしい。それはまた後ほど考える（かも）。

動かしてみた

与えられた文字列の型を判定するプログラムを書いてみた。
hso9ex - Online C# Compiler & Debugging Tool - Ideone.com
テストケースは網羅できてないけど、なんとなくいけてる感じがする。入力"01"は整数にしときたいな。オートマトンを修正しよう。
あとは、時間の型（日付時刻、年月日、時分秒...）の判定もできるようにしたい。これも後日。