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

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

状態	X	Y	Z	.

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

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

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

前回のつづき。「正規表現と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*)?$

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

こんにちははてなブログ

はてなダイアリーから引っ越ししてきたよ～！

引っ越し

はてなダイアリーが終わるらしい。
2019年春「はてなダイアリー」終了のお知らせと「はてなブログ」への移行のお願い - はてなダイアリー日記
引越しせんとな。

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

正規表現は

^[-+]?[1-9][0-9]*$

でいいんじゃないかな。これに相当する状態遷移図は

でいいんじゃないかな。S2が受理状態。S3になったら直ちにエラーとして停止していい。これを元に作ってみたC#のクラスは

interface Checker
{
  /// <summary>このオブジェクトの状態を初期状態に戻す</summary>
  void Reset();

  /// <summary>1文字読む</summary>
  /// <param name="ch">読込む文字</param>
  void Next(char ch);

  /// <summary>受理状態かどうか調べる</summary>
  /// <returns>true:受理状態, false:受理状態ではない</returns>
  bool IsAcceptable();

  /// <summary>エラー状態かどうか調べる</summary>
  /// <remarks>エラー状態になった場合、それ以降の文字を読む必要が無い</remarks>
  /// <returns>true:エラー状態, false:エラー状態ではない</returns>
  bool IsError();
}

class IntChecker : Checker
{
  enum IntParsingState
  {
    /// <summary>状態0</summary>
    State0,
    /// <summary>状態1</summary>
    State1,
    /// <summary>状態2</summary>
    State2,
    /// <summary>状態3</summary>
    State3,
  }

  IntParsingState _state;

  public IntChecker()
  {
    Reset();
  }

  public void Reset()
  {
    _state = IntParsingState.State0;
  }

  public void Next(char ch)
  {
    switch (_state)
    {
      case IntParsingState.State0:
        if (ch == '-' ||
          ch == '+')
        {
          _state = IntParsingState.State1;
        }
        else if (ch == '1' ||
          ch == '2' ||
          ch == '3' ||
          ch == '4' ||
          ch == '5' ||
          ch == '6' ||
          ch == '7' ||
          ch == '8' ||
          ch == '9')
        {
          _state = IntParsingState.State2;
        }
        else
        {
          _state = IntParsingState.State3;
        }
        break;
      case IntParsingState.State1:
        if (ch == '1' ||
          ch == '2' ||
          ch == '3' ||
          ch == '4' ||
          ch == '5' ||
          ch == '6' ||
          ch == '7' ||
          ch == '8' ||
          ch == '9')
        {
          _state = IntParsingState.State2;
        }
        else
        {
          _state = IntParsingState.State3;
        }
        break;
      case IntParsingState.State2:
        if (ch == '0' ||
          ch == '1' ||
          ch == '2' ||
          ch == '3' ||
          ch == '4' ||
          ch == '5' ||
          ch == '6' ||
          ch == '7' ||
          ch == '8' ||
          ch == '9')
        {
          _state = IntParsingState.State2;
        }
        else
        {
          _state = IntParsingState.State3;
        }
        break;
      case IntParsingState.State3:
        _state = IntParsingState.State3;
        break;
    }
  }

  /// <summary>受理状態かどうかを判断する</summary>
  /// <returns></returns>
  public bool IsAcceptable()
  {
    return _state == IntParsingState.State2;
  }


  public bool IsError()
  {
    return _state == IntParsingState.State3;
  }
}

でいいんじゃないかな。これを

Checker checker = new IntChecker();
string str = "+123";
foreach (char ch in str)
{
  checker.Next(ch);
  if (checker.IsError())
  {
    break;
  }
}

if (checker.IsAcceptable()) {
  Console.WriteLine("整数だよ");
}
else
{
  Console.WriteLine("整数じゃないよ");
}

こんな感じで使ってみたりなんかしちゃって。
実数でも同じことしたい。実数を表す文字列の正規表現は

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

でよさげだけど、今のところ状態遷移図を描けてない。ちょっと考える。

数式の結果が更新されない問題の回避方法

セルの値が正しく表示されない問題「数式の結果が更新されない - チキン煮込みチーズミックス4辛」を書いたが、回避の方法を見つけた。
数式内で、次のようにシート名まで書くと、問題は起こらないようだ。理由は不明。

=concat(Sheet1!A2:A21)

やっぱり無理だった

一回うまくいった気がしたけど。勘違いだった。もしくは、本当に上手くいったけど、再現性がない？
とにかく、まだ解決しない。