プログラミング言語で使われる正規表現は、オートマトン理論から派生したものですがオートマトン理論でいう正規表現とプログラミング言語でいう正規表現とでは意味合いが異なります。このセミナーでは、まず、オートマトン理論における正規表現を紹介し、その後にプログラミング言語における正規表現を解説します。

オートマトン理論における正規言語(regular language)は、有限オートマトンあるいは有限状態機械(finite state machine)で認識される言語のことです。ここで言語というのは、認識する文字列の集合のことです。

例えば、「わたしはにんげんです。」は日本語ですが、「たしわにげんすでん。」は日本語ではありません。そこで、理論的には日本語というものを、日本語として解釈可能な文字列の集合として定義するのです。

正規言語というのは（コンピュータ・サイエンスを本格的にやっていない私が言うのもアレですが）学問の基礎中の基礎なのでそんなに大したものではないです。まあ、リラックスしてやりましょう。

有限オートマトンの定義

有限オートマトン(finite automaton)を次の５つ組で定義します。

状態(state)とよばれる有限集合
アルファベット(alphabet)と呼ばれる有限集合
状態とアルファベットを引数にとり、状態を戻り値とする遷移関数(transition function)
開始状態(state state)
受理状態の集合(set of accept states)

「くいなちゃん」という文字だけを受理するオートマトン

次に示す図に「くいなちゃん」という文字だけを受理するオートマトンfsm1を示します。

状態はq1からq8までの８状態あります。アルファベットはKuinで扱う文字全体とします。開始状態はq1です。受理状態はq7だけです。それではこのオートマトンを表現するプログラムを書いてみます。

automaton1.kn

enum State
	q1
	q2
	q3
	q4
	q5
	q6
	q7
	q8
end enum

func transitionFunction(state: @State, alphabet: char): @State
	if(state = %q1)
		if(alphabet = 'く')
			ret %q2
		else
			ret %q8
		end if
	elif(state = %q2)
		if(alphabet = 'い')
			ret %q3
		else
			ret %q8
		end if
	elif(state = %q3)
		if(alphabet = 'な')
			ret %q4
		else
			ret %q8
		end if
	elif(state = %q4)
		if(alphabet = 'ち')
			ret %q5
		else
			ret %q8
		end if
	elif(state = %q5)
		if(alphabet = 'ゃ')
			ret %q6
		else
			ret %q8
		end if
	elif(state = %q6)
		if(alphabet = 'ん')
			ret %q7
		else
			ret %q8
		end if
	else {stateがq7かq8のとき}
		ret %q8
	end if
end func

; この関数はオートマトンを動作させて、
; 入力の文字列を受理すればtrue, 拒否すればfalseを返します。
func runAutomaton(str: []char): bool
	var state: @State :: %q1
	for i(0, ^str - 1)
		do state :: @transitionFunction(state, str[i])
	end for
	if(state = %q7)
		ret true
	else
		ret false
	end if
end func

; この関数はオートマトンに文字列を入力し、
; 入力と結果を印字します。
func check(str: []char)
	do cui@print("入力=\"" ~ str ~ "\", 結果=")
	if(@runAutomaton(str))
		do cui@print("受理\n")
	else
		do cui@print("拒否\n")
	end if
end func

func main()
	do @check("くいなちゃん")
	do @check("くいな")
	do @check("くいなちゃんくいなちゃん")
	do @check("kuin")
end func

このプログラムは実行環境にCUIを設定して実行します。実行結果は次の通りです。

オートマトンが「くいなちゃん」という文字列を入力に取った時にだけ受理していることがわかります。このオートマトンが認識する言語を数学的に書くと、A = {"くいなちゃん"}となります。

ちなみに文字列内の\"という記述はエスケープシーケンスの一つであり、"を表します。

演習１ Kuinには「条件演算子」という演算子があります。この演算子を使って[automaton1.kn]を短くしてみてください。（ヒント：Kuinが%q1などを@State型と認識しない場合はキャストします）
演習２ [automaton1.kn]を「条件演算子」ではなく「論理積」演算子で短くしてみてください。
演習３ [automaton1.kn]のcheck関数内、do cui@print("入力=\"" ~ str ~ "\", 結果=")という記述を、~(配列連結演算子)の代わりにエスケープシーケンスを使って書き直してみてください。
**

お疲れさまでした

今回は、前回に比べてレベルが上がったように感じたのではないかと思います。Kuinの基本的な構文について不慣れな人はKuinチュートリアルを一通りこなしてみましょう。とても楽しい演習です。

演習の答え

演習１

automaton2.kn(抜粋)

func transitionFunction(state: @State, alphabet: char): @State
	if(state = %q1)
		ret alphabet = 'く' ?(%q2 $ @State, %q8 $ @State)
	elif(state = %q2)
		ret alphabet = 'い' ?(%q3 $ @State, %q8 $ @State)
	elif(state = %q3)
		ret alphabet = 'な' ?(%q4 $ @State, %q8 $ @State)
	elif(state = %q4)
		ret alphabet = 'ち' ?(%q5 $ @State, %q8 $ @State)
	elif(state = %q5)
		ret alphabet = 'ゃ' ?(%q6 $ @State, %q8 $ @State)
	elif(state = %q6)
		ret alphabet = 'ん' ?(%q7 $ @State, %q8 $ @State)
	else {stateがq7かq8のとき}
		ret %q8
	end if
end func

演習２

automaton3.kn(抜粋)

func transitionFunction(state: @State, alphabet: char): @State
	if(state = %q1 & alphabet = 'く')
		ret %q2
	elif(state = %q2 & alphabet = 'い')
		ret %q3
	elif(state = %q3 & alphabet = 'な')
		ret %q4
	elif(state = %q4 & alphabet = 'ち')
		ret %q5
	elif(state = %q5 & alphabet = 'ゃ')
		ret %q6
	elif(state = %q6 & alphabet = 'ん')
		ret %q7
	else
		ret %q8
	end if
end func

演習３

do cui@print("入力=\"\{str}\", 結果=")