さて、前回は特定の一文字を認識するオートマトンをKuin言語で作成しました。今回は、正規言語の連結演算を導入して、その応用として特定の文字列を認識するオートマトンを生成します。
今回作成したオートマトンのソースコードを示します。
; ２つのオートマトンの連結演算を行うクラス
class Concatenation(@Automaton)
+var automatonA: @Automaton {テンプレートと実働を兼ねる}
+var automatonB: @Automaton {テンプレートのみ}
+var listB: list<@Automaton> {実働}
*func ctor()
do me.listB :: #list<@Automaton>
end func
+*func isAccepted(): bool
do me.listB.head()
while(!me.listB.term())
if(me.listB.get().isAccepted())
ret true
end if
do me.listB.next()
end while
ret false
end func
+*func put(c: char)
if(me.automatonA.isAccepted())
do me.listB.add(me.automatonB.clone())
end if
do me.automatonA.put(c)
do me.listB.head()
while(!me.listB.term())
do me.listB.get().put(c)
do me.listB.next()
end while
end func
+*func clone(): @Automaton
var res: @Concatenation :: #@Concatenation
do res.automatonA :: me.automatonA.clone()
do res.automatonB :: me.automatonB.clone()
ret res
end func
end class
+func makeConcatenation(a: @Automaton, b: @Automaton): @Automaton
var res: @Concatenation :: #@Concatenation
do res.automatonA :: a.clone()
do res.automatonB :: b.clone()
ret res
end func
今回のコードから、オートマトンが並列実行される仕組みが実装されています。Concatenationクラスのメンバ変数listBは複数のオートマトンを並列実行できるようにKuinのlistというデータ構造を使用しています。Kuinのlistについては以下のドキュメントが詳しいです。
連結演算(concatenation)は数学的には次のように表されます。
A ○ B = { xy | x ∈ A かつ y ∈ B }
具体的には、「くいな」という文字列を認識する言語と「ちゃん」という文字列を認識する言語を連結演算すると「くいなちゃん」という文字列を認識する言語になります。
ソースコード内に、「テンプレート」と「実働」という言葉が出てきていますが、「テンプレート」というのはAutomatonクラスが「言語」として扱われているということで、「実働」というのはAutomatonクラスが有限オートマトンとして扱われているということを示しています。言語というのは、受理する文字列の集合のことなので状態を持ちません。しかし有限オートマトンは状態を持っています。言語とオートマトンのクラスを分けてもよかったのですが、単に状態以外のメンバをコピーすればオートマトンを複製できるのであえて言語とオートマトンを同じクラスで扱っています。
今回作成した連結演算をテストするコードを示します。
; test_concatenation1.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
var automaton: \automaton@Automaton
func check(str: []char)
var res: []char ::
|@runAutomaton(@automaton, str) ?("受理", "拒否")
do cui@print("入力=\"\{str}\", 結果=\{res}\n")
end func
func main()
alias a: \automaton@Automaton
var ku: a :: \automaton@makeOneChar('く')
var i: a :: \automaton@makeOneChar('い')
var kui: a :: \automaton@makeConcatenation(ku, i)
do @automaton :: kui
do cui@print("check kui:\n")
do @check("")
do @check("く")
do @check("い")
do @check("くい")
do @check("くいな")
var kuinachan: a
|::
|\automaton@makeConcatenation(\automaton@makeOneChar('く'),
|\automaton@makeConcatenation(\automaton@makeOneChar('い'),
|\automaton@makeConcatenation(\automaton@makeOneChar('な'),
|\automaton@makeConcatenation(\automaton@makeOneChar('ち'),
|\automaton@makeConcatenation(\automaton@makeOneChar('ゃ'),
|\automaton@makeOneChar('ん'))))))
do @automaton :: kuinachan
do cui@print("check kuinachan:\n")
do @check("")
do @check("く")
do @check("くい")
do @check("くいな")
do @check("くいなち")
do @check("くいなちゃ")
do @check("くいなちゃん")
do @check("くいなちゃんく")
do @check("くいなちゃんくいなちゃん")
end func
結果は次の通りです。
まず最初に、「く」を認識するオートマトンと「い」を認識するオートマトンを連結演算して「くい」という文字列を認識するオートマトンを生成しています。次に、「く」、「い」、「な」、「ち」、「ゃ」、「ん」をそれぞれ認識するオートマトンを連結演算によって結合し、「くいなちゃん」という文字列を認識するオートマトンを生成し、テストしています。２つのケースで正しく動作していることが分かると思います。
正規言語の演算には、連結演算のほかに、和集合演算とスター演算があります。これらを組み合わせることで複雑なパターンを認識する有限オートマトンを生成することができます。
とはいえ、今回のセミナーで解説しているソースコードは、有限オートマトンの理論を愚直に取り扱ったものなので一般的に使われている正規表現ライブラリに比べてはるかに遅いです。しかし、正規表現の思想には正規言語が大きくかかわっていることを理解するために今回は理論を愚直に書き下したソースコードを示しています。