CSセミナー003 一文字を受け取るオートマトン

さて、正規言語について一気に説明するために非決定性オートマトンというものを導入します。これは複数のオートマトンが同時並行的に動作するオートマトンです。複数のオートマトンを扱うためにクラスを使います。クラスの基本的な使い方については「Kuinでクロージャ」という記事をご覧ください。

さて、ある特定の一文字を認識する有限オートマトンを考えます。これは３つの状態で実現できます。初期状態と受理状態（指定した文字１文字を受け取った状態）とその他の状態の３つです。

ソースコードへのリンク

automaton.knがオートマトンの本体で、test_onechar.knがテストコードです。automaton.knは回を重ねるごとにコードが追加されていきます。Kuinエディタでtest_onechar.knを実行すると一文字を認識するオートマトンのテストを行います。

test_onechar.kn

func runAutomaton(automaton: \automaton@Automaton, str: []char): bool
    var a: \automaton@Automaton :: automaton.clone()
    for i(0, ^str - 1)
        do a.put(str[i])
    end for
    ret a.isAccepted()
end func

func check(str: []char)
    var res: []char ::
    |@runAutomaton(\automaton@makeOneChar('く'), str) ?("受理", "拒否")
    do cui@print("入力=\"\{str}\", 結果=\{res}\n")
end func

func main()
    do @check("")
    do @check("く")
    do @check("くい")
    do @check("い")
end func

\automaton@makeOneChar関数で一文字を認識するオートマトンを生成することができます。このテストコードでは、「く」を認識するオートマトンを生成し、４つの場合についてテストしています。テスト結果は以下の通りです。