CSセミナー005 正規言語の和集合演算・スター演算

今回は、正規言語の演算のうち、和集合演算とスター演算について説明します。

今回のソースコード

和集合演算

正規言語の和集合演算を数式で記述すると次のようになります。
A ∪ B = { x | x ∈ A または x ∈ B }
例えば、「みかん」という文字列を認識する言語と「りんご」という文字列を認識する言語を和集合演算すると、「みかん」と「りんご」の両方を認識する言語になります。

ソースコードを次に示します。

automaton.kn(抜粋)

; ２つのオートマトンの和集合演算を行うクラス
class Union(@Automaton)
	+var automatonA: @Automaton
	+var automatonB: @Automaton
	
	+*func isAccepted(): bool
		ret me.automatonA.isAccepted() | me.automatonB.isAccepted()
	end func
	
	+*func put(c: char)
		do me.automatonA.put(c)
		do me.automatonB.put(c)
	end func
	
	+*func clone(): @Automaton
		var res: @Union :: #@Union
		do res.automatonA :: me.automatonA.clone()
		do res.automatonB :: me.automatonB.clone()
		ret res
	end func
end class

+func makeUnion(a: @Automaton, b: @Automaton): @Automaton
	var res: @Union :: #@Union
	do res.automatonA :: a.clone()
	do res.automatonB :: b.clone()
	ret res
end func

テストコードを次に示します。

test_union1.kn

; test_union1.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 toAutomaton(str: []char): \automaton@Automaton
	var res: \automaton@Automaton
	do res :: \automaton@makeOneChar(str[0])
	for i(1, ^str - 1)
		do res :: \automaton@makeConcatenation(
		|res, \automaton@makeOneChar(str[i]))
	end for
	ret res
end func

func main()
	alias a: \automaton@Automaton
	do cui@print("test kuina or chan\n")
	do @automaton :: \automaton@makeUnion(
	|@toAutomaton("くいな"), @toAutomaton("ちゃん"))
	do @check("")
	do @check("くいな")
	do @check("ちゃん")
	do @check("くいなちゃん")
	do @check("く")
	do @check("ち")
	do cui@print("test kuinachan or rokusai\n")
	do @automaton :: \automaton@makeUnion(
	|@toAutomaton("くいなちゃん"), @toAutomaton("６さい"))
	do @check("")
	do @check("くいな")
	do @check("ちゃん")
	do @check("くいなちゃん")
	do @check("６さい")
	do @check("くいなちゃん６さい")
end func

実行結果を次に示します。

スター演算

スター演算はある言語の繰り返しを認識する言語を生成する演算です。数式で示すと以下のようになります。
A* = { x1 x2 ... xk | k ≥ 0 で、各々の xi について xi ∈ A }
例えば、「くいなちゃん」という文字列を認識する言語にスター演算を適用すると、空文字列「」、「くいなちゃん」、「くいなちゃんくいなちゃん」などを認識する言語が生成されます。

次にソースコードを示します。

automaton.kn(抜粋)

; オートマトンのスター演算を行うクラス
class Star(@Automaton)
	+var automaton: @Automaton {テンプレート}
	+var listA: list<@Automaton> {実働}
	
	*func ctor()
		do me.listA :: #list<@Automaton>
	end func
	
	+*func isAccepted(): bool
		if(^me.listA = 0)
			ret true
		end if
		do me.listA.head()
		while(!me.listA.term())
			if(me.listA.get().isAccepted())
				ret true
			end if
			do me.listA.next()
		end while
		ret false
	end func
	
	+*func put(c: char)
		if(^me.listA = 0)
			do me.listA.add(me.automaton.clone())
		else
			do me.listA.head()
			while loop(!me.listA.term())
				if(me.listA.get().isAccepted())
					do me.listA.add(me.automaton.clone())
					break loop
				end if
				do me.listA.next()
			end while
		end if
		do me.listA.head()
		while(!me.listA.term())
			do me.listA.get().put(c)
			do me.listA.next()
		end while
	end func
	
	+*func clone(): @Automaton
		var res: @Star :: #@Star
		do res.automaton :: me.automaton
		ret res
	end func
end class

+func makeStar(a: @Automaton): @Automaton
	var res: @Star :: #@Star
	do res.automaton :: a
	ret res
end func

スター演算の実装の仕方は連結演算のそれに似ています。空文字列の扱いは少しトリッキーになっています。

次にテストコードを示します。

test_star1.kn

; test_star1.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 toAutomaton(str: []char): \automaton@Automaton
	var res: \automaton@Automaton
	do res :: \automaton@makeOneChar(str[0])
	for i(1, ^str - 1)
		do res :: \automaton@makeConcatenation(
		|res, \automaton@makeOneChar(str[i]))
	end for
	ret res
end func

func main()
	alias a: \automaton@Automaton
	do cui@print("test kuina*\n")
	do @automaton :: \automaton@makeStar(@toAutomaton("くいな"))
	do @check("")
	do @check("くいな")
	do @check("くいなくいな")
	do @check("くいなくいなくいな")
	do @check("くいなくいなくいなちゃん")
	do cui@print("test (kuina or rokusai)*\n")
	do @automaton :: \automaton@makeStar(
	|\automaton@makeUnion(@toAutomaton("くいな"), @toAutomaton("６さい")))
	do @check("")
	do @check("くいな")
	do @check("ちゃん")
	do @check("６さい")
	do @check("くいなちゃん６さい")
	do @check("くいな６さい")
	do @check("くいな６さい６さいくいな")
end func

次に実行結果を示します。

まとめ

有限オートマトンと、それに関する３つの演算（連結演算・和集合演算・スター演算）を示しました。有限オートマトンに対してこれらの演算を適用しても有限オートマトンが得られることが分かっています。示したソースコードでは定義を満たす最も簡潔な実装を行っているので実行効率は悪いものとなっています。

正規言語は有限オートマトンで認識可能な言語のことです。プログラミング言語で用いられている正規表現は正規言語のアイディアがもとになっていますが、より実用的なインターフェースが用意されており、アルゴリズムの工夫により高速に動作するようになっています。次回は、Kuinの正規表現ライブラリについて学んでみましょう。