プログラミング言語で使われる正規表現は、オートマトン理論から派生したものですがオートマトン理論でいう正規表現とプログラミング言語でいう正規表現とでは意味合いが異なります。このセミナーでは、まず、オートマトン理論における正規表現を紹介し、その後にプログラミング言語における正規表現を解説します。
オートマトン理論における正規言語(regular language)は、有限オートマトンあるいは有限状態機械(finite state machine)で認識される言語のことです。ここで言語というのは、認識する文字列の集合のことです。
例えば、「わたしはにんげんです。」は日本語ですが、「たしわにげんすでん。」は日本語ではありません。そこで、理論的には日本語というものを、日本語として解釈可能な文字列の集合として定義するのです。
正規言語というのは（コンピュータ・サイエンスを本格的にやっていない私が言うのもアレですが）学問の基礎中の基礎なのでそんなに大したものではないです。まあ、リラックスしてやりましょう。
有限オートマトンの定義
有限オートマトン(finite automaton)を次の５つ組で定義します。
- 状態(state)とよばれる有限集合
- アルファベット(alphabet)と呼ばれる有限集合
- 状態とアルファベットを引数にとり、状態を戻り値とする遷移関数(transition function)
- 開始状態(state state)
- 受理状態の集合(set of accept states)
「くいなちゃん」という文字だけを受理するオートマトン
次に示す図に「くいなちゃん」という文字だけを受理するオートマトンfsm1を示します。
状態はq1からq8までの８状態あります。アルファベットはKuinで扱う文字全体とします。開始状態はq1です。受理状態はq7だけです。それではこのオートマトンを表現するプログラムを書いてみます。
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チュートリアルを一通りこなしてみましょう。とても楽しい演習です。
演習の答え
演習１
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
演習２
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}\", 結果=")