モジュール詳細：有限オートマトン

ステートマシンについて勉強しておいてくださいね。さもないと、この爆弾の状態が「爆発済み」に遷移してしまうかもしれませんから。

このモジュールでは、シリアルナンバーに基づいて1つ以上の正規表現を選択し、それらを有限オートマトンに変換し、それらに演算を適用する。最初の5つの画面には5つの正規表現が表示され、最後の画面は送信パネルである。

用語

• 正規表現:記号 a, b, ε (イプシロン、テキストが空であることを表す)と演算子(下記参照)から構成される文字列。
• 有限オートマトン: 状態およびそれらの間の遷移から成る集合であり、正規表現と相互変換が可能である。各遷移には英字1文字が関連し、ここでは「a」または「b」のどちらかのみ出現する。これは、その遷移がどの入力に従うかを制御するために用いられる。
• 遷移グラフ: 有限オートマトンに似た構造を持つが、「a」と「b」のみではなく、遷移には任意の正規表現を関連付けることができる。ここでは、有限オートマトンを作成するプロセスにおける一歩として用いられる。

正規表現の演算と構文

R とS は任意の正規表現である。

1. 括弧：(R) 例：(a), (b)
2. クリーネスター：R* 例： a*, (ab)*
3. 結合：RS 例： ab, ab*, b*a
4. 選択：R|S 例： a|b, a*|ab

注意点として、選択の最後の例については、オペランド(演算対象)は、a* とab となる。これは、オペランドの優先順位によるものである。同様に、結合の最後の例について、右のオペランドはb* であり、クリーネスターの二つ目の例については、オペランドは(ab) である。また、もう一点付け加えると、 * は単項演算子であり、右側にオペランドを持たない。そのためb*a は b* とa の結合として解釈される。

下記のアルゴリズムにおいて、「最も外側の演算子」とは、括弧の中に含まれていない正規表現内で最後に演算する演算子を指す。具体的には、正規表現ab|a(ab*|a)b について、最も外側の演算子は括弧の外側にある選択演算子を指す。このような演算子が複数ある場合、次ページで説明しているアルゴリズムについては、そのような演算子からいずれかを選択してよい。

使用する正規表現と演算子の特定

使用する正規表現を特定するには、シリアルナンバーの数字を確認する。

シリアルナンバーに数字が奇数個含まれている場合:

1. 真ん中に位置する数字を5で割る。
2. その余りが、有限オートマトンの変換に必要な正規表現である。
3. 真ん中に位置する数字が5以上である場合、結果の有限オートマトンの補集合を取る。そうでない場合、前のステップで得たオートマトンが最終的な答えとなる。

シリアルナンバーに数字が偶数個含まれている場合:

1. シリアルナンバーの最初の数字と最後の数字を5で割る。
2. その余りが、有限オートマトンの変換に必要な2つの正規表現である。
3. シリアルナンバーの最初の数字が5以上である場合、1つ目のオートマトンの補集合を取得する。
4. シリアルナンバーの最後の数字が5以上である場合、2つ目のオートマトンの補集合を取得する。
5. 最後の数字が最初の数字より小さい場合、2つのオートマトンの積集合を取得する。そうでない場合、2つのオートマトンの和集合を取得する。その結果が最終的な答えとなる。

結果は、次のページに示されている形式で、モジュール内の表の欄に入力していく。

正規表現から有限オートマトンへの変換

正規表現を有限オートマトンに変換するプロセスは以下の通りである。

• 2つの状態と1つの遷移を持ち、開始状態から終了状態へと完全な正規表現に沿って遷移する遷移グラフを作成する。
• (任意) いずれかの時点で、2つの遷移の正規表現と開始状態と終了状態が同じ場合、重複した遷移を削除できる。
• (任意) いずれかの時点で、2つの状態について、それらがすべて同じ正規表現ラベルで同じ遷移先へ向かう遷移を持っているかつ、2つが両方とも受理状態である又はどちらも受理状態でない場合、2つのうち一方の状態が遷移先であるすべての遷移について、もう一方の状態に置き換えてもよい。その後、付け替えられた状態は削除できる。

次のページに続く...

• (任意) いずれかの時点で、任意の回数遷移しても受理状態に到達できない状態がある場合、その状態を削除できる。

• (任意) 到達不可能な状態は、いつでも削除できる。

  状態が「到達可能」であるとは、ある開始状態から状態への経路があることを指す。そうでない場合、その状態は「到達不可能」である。

• 正規表現が a, b, ε 以外の遷移がなくなるまで、以下の手順を繰り返す。
  • その遷移のうち1つを選ぶ。これを e と呼ぶ。
  • e の正規表現について、最も外側の演算子を特定する。
    • その正規表現の最も外側の演算子が式全体を囲む括弧である場合、括弧を削除し、このリストの下に進む。
    • 最も外側の演算子が、ある正規表現 R のクリーネスター R* である場合、以下の手順を行う。
      1. 状態を1つ追加する。
      2. e から、新しい状態へ ε 遷移で接続する。
      3. 新しい状態から e の遷移先へ ε 遷移で接続する。
      4. 新しい状態から新しい状態(自分自身)へ R 遷移で接続する。
      5. e を削除する。
    • 最も外側の演算子が、ある正規表現 R と S の選択 R|S である場合、以下の手順を行う。
      1. e の正規表現を R に置き換える。
      2. e の遷移元から e の遷移先へ、正規表現 S で遷移する遷移を追加する。
    • 最も外側の演算子が、ある正規表現 R と S の結合 RS である場合、以下の手順を行う。
      1. 状態を1つ追加する。
      2. e の遷移元から新しい状態へ、正規表現 R で遷移する遷移を追加する。
      3. 新しい状態から e の遷移先へ、正規表現 S で遷移する遷移を追加する。
      4. e を削除する。
• 正規表現が ε である遷移 e に対して、それぞれ以下の処理を行う。
  1. A を e の遷移元、B を e の遷移先とする。
  2. B を遷移元とする遷移 s に対して、 s のコピーを作成し、その遷移元を A にする。

• 3. A を遷移先とする遷移 t に対して、 t のコピーを作成し、その遷移先を B にする。
  4. B が受理状態である場合、A も受理状態にする。
  5. e を削除する。
• 同じ正規表現で複数の遷移が存在する状態 S に対して、それぞれ以下の処理を行う。
  1. 新たな状態を作成する。
  2. 状態 S から、その正規表現で遷移する遷移tごとに、
     • t の遷移先が受理状態である場合、新たな状態を受理状態に設定する。
     • t の遷移先を遷移元とする各遷移に対して、コピーを作成し、その遷移元を新たな状態に設定する。
  3. 状態 S から、その正規表現で遷移するすべての遷移を削除する。
  4. S から、新たな状態へ、それと同じ正規表現で遷移する新しい遷移を1つ追加する。
• 遷移先が a でも b でもない遷移が最低一つ存在する場合、

1. 新しい状態を追加し、これをBとする。
2. B から自分自身へ a で遷移する遷移と b で遷移する遷移を追加する。
3. a で遷移する遷移か b で遷移する遷移が存在しない状態に対して、その状態から Bへ、その正規表現で遷移する新しい遷移を追加する。

有限オートマトンの演算

有限オートマトンに対して適用できる3つの集合演算がある。以下は、その一覧と評価方法を示している。

• 補集合演算: この操作が適用された有限オートマトンの状態それぞれについて、受理状態の有無を反転させる。つまり、元々受理状態だったもの以外を、すべて受理状態する。
• 和集合演算:
  • 簡易版: もし入力オートマトンの一方の状態がすべて受理状態であるか、一方の入力オートマトンがもう一方の補集合であるなら、到達可能な状態がすべて受理状態である任意の有限オートマトンは受理される。
  • 簡易版: もし入力オートマトンの一方に到達可能な受理状態が全くないか、両方とも等しいなら、もう一方の入力オートマトンが受理される。
  1. 新しい有限オートマトンを作成する。このオートマトンは、演算が適用される有限オートマトンの2状態を1つのペアとし、それを状態として持つ。以降、この状態を「グループ状態」と呼ぶ。
  2. 新しいオートマトンに開始状態となるグループ状態を1つ追加する。

• 2. この状態は、2つの入力オートマトンの開始状態のペアを設定する。
  3. 入力オートマトンのいずれかの開始状態が受理状態であれば、開始グループ状態も受理状態とする。
  4. 各入力オートマトンに対応する状態から、aで遷移する遷移と、bで遷移する遷移の2つを確認する。そして、それぞれの入力が到達する状態を調べる。
     • グループ状態には、対応する2つのオートマトンの状態に対応する番号を付けられる。例えば、オートマトンAの状態1がa遷移で状態2に遷移し、オートマトンBの状態1がa遷移で状態3に遷移する場合、出力オートマトンは状態(1,1)から状態(2,3)へaで遷移する遷移を持つ。
  5. 見つけた状態のペアに対応するグループ状態が存在しなければ、それに対応する新しいグループ状態を追加する。
  6. ペア内のどちらかの状態がその有限オートマトンで受理状態であれば、グループ状態も受理状態とする。
     • 例えば、オートマトンBの状態3が受理状態なら、グループ状態(2,3)も受理状態となる。
  7. 一つ前のグループ状態からこのグループ状態へ、対応する正規表現で遷移する遷移が存在しなければ、その遷移を追加する。
     • 上の例では、状態(1,1)から状態(2,3)へaで遷移する遷移を追加することになる。
  8. この手順を、ステップ4以降で新たに追加された各グループ状態ごこに繰り返し、追加すべき新しいグループ状態がなくなるまで続ける。その後、次に進む。
• 9. 各グループ状態について、番号を割り当てる。同じグループ状態が現れる箇所は、すべて対応する番号に置き換える。これが結果のオートマトンである。

• 積集合演算:
  • 簡易版: 一方の入力オートマトンに受理状態が全く無い場合、結果は、到達可能な受理状態が全く無い任意の有限オートマトンを指定できる。
  • 簡易版: 入力オートマトンの一方のすべての状態が受理状態である場合、結果は他方の入力オートマトンと等しい。
  • 簡易版: 2つの入力オートマトンが等しい場合、結果も等しい。
  • 簡易版: 2つの入力オートマトンが互いに補集合である場合、結果は、到達可能な受理状態が全く無い任意の有限オートマトンを指定できる。
  1. 上の和集合の手順と同じプロセスを実行する。ただし、ペアの両方の状態が受理状態である場合のみ、グループ状態を受理状態にする。

入力形式の例

以下に示す3つの状態間の遷移を持つ有限オートマトンを考える。状態1が開始状態であり、状態3が受理状態であるとする。

入力形式は以下の表で示している。右2列は、左端の列に示された起点状態から、列が示す遷移で進んだ先の状態を表す。
左端の列の数字の前にある > は開始状態を示し、+ は受理状態を示す。状態が開始状態かつ受理状態である場合は、状態番号の前に >+ を示して表す。

起点状態	a	b
>1	3	2
2	1	3
+3	2	1

なお、行は常に追加できるが、削除することはできない。空白の行は無視される。数字を入力するには、セルをクリックして値を順に切り替える。開始状態または受理状態を設定するには、左端の列の状態番号をクリックする。上下矢印を使って表示される行を変更する。