さて、前回は特定の一文字を認識するオートマトンをKuin言語で作成しました。今回は、正規言語の連結演算を導入して、その応用として特定の文字列を認識するオートマトンを生成します。

今回のソースコード

今回作成したオートマトンのソースコードを示します。

automaton.kn(抜粋)

; ２つのオートマトンの連結演算を行うクラス
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については以下のドキュメントが詳しいです。

Kuin逆引き辞典3 各種データ構造を扱う

連結演算(concatenation)は数学的には次のように表されます。

A ○ B = { xy | x ∈ A かつ y ∈ B }

具体的には、「くいな」という文字列を認識する言語と「ちゃん」という文字列を認識する言語を連結演算すると「くいなちゃん」という文字列を認識する言語になります。

ソースコード内に、「テンプレート」と「実働」という言葉が出てきていますが、「テンプレート」というのはAutomatonクラスが「言語」として扱われているということで、「実働」というのはAutomatonクラスが有限オートマトンとして扱われているということを示しています。言語というのは、受理する文字列の集合のことなので状態を持ちません。しかし有限オートマトンは状態を持っています。言語とオートマトンのクラスを分けてもよかったのですが、単に状態以外のメンバをコピーすればオートマトンを複製できるのであえて言語とオートマトンを同じクラスで扱っています。

今回作成した連結演算をテストするコードを示します。

test_concatenation1.kn

; 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

結果は次の通りです。

まず最初に、「く」を認識するオートマトンと「い」を認識するオートマトンを連結演算して「くい」という文字列を認識するオートマトンを生成しています。次に、「く」、「い」、「な」、「ち」、「ゃ」、「ん」をそれぞれ認識するオートマトンを連結演算によって結合し、「くいなちゃん」という文字列を認識するオートマトンを生成し、テストしています。２つのケースで正しく動作していることが分かると思います。

正規言語の演算には、連結演算のほかに、和集合演算とスター演算があります。これらを組み合わせることで複雑なパターンを認識する有限オートマトンを生成することができます。

とはいえ、今回のセミナーで解説しているソースコードは、有限オートマトンの理論を愚直に取り扱ったものなので一般的に使われている正規表現ライブラリに比べてはるかに遅いです。しかし、正規表現の思想には正規言語が大きくかかわっていることを理解するために今回は理論を愚直に書き下したソースコードを示しています。