二次元配列で高速な決定性有限オートマトン

公開日:2018-10-15
最終更新:2018-10-24
※この記事は外部サイト(https://kze.hatenadiary.jp/entry/2016/09/1...)からのクロス投稿です

 ズンドコチェックを実装するときに決定性有限オートマトンを使った記事です。

夫:僕だったらズンドコチェックは白と黒の扉を使って実装するな。

私:それってオートマトンと形式言語についての入門書、白と黒のとびらの?応用できるの?

夫:うん。部屋の状態を二次元配列にすれば解ける。

私:ちょっと待って、自分で考えて実装してみる。

 というわけで、状態遷移図を書きながら、次のようなプログラムを作ったわけです。

 ちなみに部屋とは何かなんですが、この白と黒のとびらという本では、オートマトンの状態を部屋に、入力を扉に例えています。

def sing

  phrase1 = "ズン"
  phrase2 = "ドコ"

  if Random.rand > 0.5 then
    puts phrase1
    return phrase1
  else
    puts phrase2
    return phrase2
  end
end

room = [[1,0],[2,0],[3,0],[4,0],[4,5],[nil]]

i = 0

until room[i] == [nil] do
  if sing == "ズン" then
    i = room[i][0]
  else
    i = room[i][1]
  end
end

puts "き・よ・し!"

 まず、配列 room ですが、この room の添え字がそのまま部屋番号になります。0号室から5号室まで、全部で6つの部屋があります。

 次に、この部屋にはズンとドコのとびらがあります。i号室のズンのとびらは room[i][0] 、 ドコのとびらは room[i][1] です。

 そして、配列の各要素には移動先の部屋番号が書いてあります。例えば、4号室に居るときにズンのとびらを開いたら4号室にまた戻ってきます。ドコのとびらを開いたら5号室に移動します。最後の部屋にはこの部屋が最後だと示すためのnilを入れます。

 こうすることで、ズンかドコを0回以上繰り返した後ズンを4回以上繰り返してからドコで終わる文だけを受け入れる決定性有限オートマトンが出来上がりました。

私:ところで、このプログラムは何が利点なの?

夫:超速い。あと、配列 room の中身だけ直せば他の文にも対応できる。君が書いたお話にはこのプログラムを取り入れることはできないだろうけど、こういうものもあるよと。

私:なるほど。

 私にとっては速さよりも本で学んだことが早速活かせたことが楽しかったです。

記事が少しでもいいなと思ったらクラップを送ってみよう!
54
+1
@rotelstiftの技術ブログ

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする