正規表現2（状態遷移図とオートマトンで遊ぶ）
このページはマス旅の一部です。
状態遷移図、オートマトン。
これらは、いろんな場面で聞くコトバですね。
イベントや条件判断によって、場合分けして状態を移り進む
仕組みや図というイメージです。（正確な定義はあとに回します。）
よくあるたとえが「自動販売機の反応」、「パスカルの三角形を剰余で色分けする」などですね。
シェルピンスキーでセルオートマトンをやりました。忘れている人はざっと目を通しておきましょう。
さて、前回はクリーネ代数から正規表現が始まったことをやり、
合成数判定で、正規表現を使うと
まるで「再帰的と言えるような検索」ができる体験をしましたね。
「正規表現は、ツリーのトラバースや状態遷移図につながる」と言われてもピンとくるでしょう。
そこのところを、さらに調べてみよう。
１．まずは基本から
＜FA＞
オートマトンAは入力を1文字ずつ読みながら状態を移り、最終的に「受理」か「拒否」を判定するものです。
有限オートマトンFAは「状態を覚えながら1文字ずつ読む判定機」で、５つ組（状態集合Q、入力記号Σ、遷移関数δ、初期状態q0、受理状態F）を持ちます。
q0,Fはもちろん、Qの要素だから、特に最初の3要素がベースになりますね。
状態遷移図の読み方は省略します。
くわしくはこちら（状態発生をモデル化）の「状態遷移図」
また、FAは決定性DFAと非決定性NFAに2分されます。
＜DFA＞
DFAのD（Deterministic決定性）は何が決まっているということでこの名がついているかです。
それぞれの状態Qでそれぞれの入力記号Σに対して、どの状態Qに移るかがはっきり一意的に決まるというのが決定性があるということです。
つまり、δ：Q×Σ→Qが関数と言えるものです。
たとえば、
５つの組（Q,Σ、δ、q0、F）のうち、δ以外を決めてみる。
Σ＝{0,1},Q={q0:直前が１,q1:直前が0、q2:=[01]を見つけた=F}
q0で1を読むと、この1が「直前が1」の意味となるから、q0状態のままとなり、自己ループにはまる。
q0で0を読むと、この0が「直前が0」の意味となるから、q1状態に移る。q1にいて0を読んでも「直前が0」の意味となるから、q1から抜けられないが、q1にいて1を読むと[01]を見つけたから、q2に移動し、受理状態となる。q2に到達したあとは、次に0が来ても1が来ても[01]を含んでいることには変わりないので、q2に留まり続けます
このように、関数δ(qi,j)=qkで、i,jからkが１つに決まるので、これはDFAと言えるね。
＜NFA＞
NFAのN(Non)は一意的な状態への移動が決まるの否定です。
だから、１つの状態の否定だから、複数の状態や0個の状態も
ありという、あいまいなマシンです。
つまり、空集合も入れた状態Qのあらゆる部分へ移動できます。
言い換えると、Qの部分集合、P(Q)の中のどれか1つの集合に一斉に移る（状態のアンサンブル・並行世界）ということです。状態集合Qのサイズがnならば、2^n通りの可能性があるということですね。
ぜんぜん別世界に見えますが、当たるも八卦当たらぬも八卦、
いろいろやってみてうまくいったらラッキーという進み方ができるということですね。もちろん、行き止まりでアウトということもあります。
これはDFAには自己ループがあり受理できない場合があるので、NFAだからダメだということにはなりません。
前回の例でいうと、強欲マッチは１つの最長を決めますが、
無欲マッチはまったり粘り強く可能性を広げましたね。
この違いはDFAとNFAの違いに似てますね。
２．NFAをDFAにする
NFAはゆるく無欲なので、書きやすそうですね。
DFAは明確なので受理判定が速そうですね。
そのいいとこどりができます。
人間がNFAで書いた表現をDFAに変換してからPCに実行してもらうのです。
＜べき集合構成＞
実際NFAはPC内部でDFAに変換されて実行されているそうです。
そこで活躍するのが「べき集合」です。
人間がNFAをプログラミングによってDFAに変換することもできるでしょう。
NFAの初期状態q0をそのままDFAの初期状態q0とします。
NFAの状態集合Qから作ったべき集合P(Q)＝Q'をDFAの状態集合とします。
新状態Q'のうちNFAの受理状態Fを含む状態すべてがDFAの受理状態集合F'となります。
NFAの「状態の組み合わせ（集合）」を、DFAの「1つの新しい状態」とみなす操作を
「べき集合構成」と言います。
＜ムーアのアルゴリズム＞
実際は状態の数が膨大になるので、
受理群と非受理群に状態をグループ分けして、
文字を入れてそれぞの文字の行先が同じグループになるかどうかで、
グループを2分します。これを繰り返すと分割が起きなくなります。
この機能としての状態遷移図（遷移関数）の簡略化を図ることにより、
最小DFAが得られるそうです。
＜正規表現（有限オートマトン）の限界＞
a^n b^n（aをn個並べた後にbを同じだけ並べる）は正規表現ではできないのです。
「正規表現でHTMLパースはするな」
という格言につながりますね。
コンパイラの構文解析やHTMLのタグ対応にはプッシュダウン・オートマトン（スタック）が必要ですが、TCPプロトコル解析や単純なデータ切り出しなど、入れ子構造がない場面では
正規表現（有限オートマトン）
が実質的な標準として大活躍しています。
３．コード化
課題：import re に頼らず、状態遷移表で「aが偶数個あるか判定するDFA」などを再現してみよう。文字集合Σ＝{a,b,c,d}とします。
＜Python＞
#aが偶数個あると受理するDFA
#Σ={a,b,c,d}
#q_even(偶数個状態)=F(受理）,q_odd(奇数個状態),q0(開始)=q_even扱い
#qcur(現在),qnext(次)
def transit(cur, char):
# アルファベットの定義
alphabet = {'a', 'b', 'c', 'd'}
# 定義外の文字が来たら、またはすでにエラー状態なら、エラー状態を維持
if char not in alphabet or cur == 'q_err':
return 'q_err'
# aが来たら状態を反転
if char == 'a':
if cur == 'q_even':
return 'q_odd'
if cur == 'q_odd':
return 'q_even'
# b, c, d の場合は現在の状態（q_even / q_odd）を維持
return cur
def DFA(target):
# 最初から「q_even（偶数個状態）」でスタートする
cur = 'q_even'
for item in target:
cur = transit(cur, item)
# 最終的に q_even の場合のみ受理（True）とする
return cur == 'q_even'
# --- テスト実行 ---
test_cases = [
"", # aは0個 (偶数) -> True
"bcd", # aは0個 (偶数) -> True
"ab", # aは1個 (奇数) -> False
"aba", # aは2個 (偶数) -> True
"aacaada", # aは4個 (偶数) -> True
"abcdaaaa", # aは5個 (奇数) -> False
"abx" # 定義外の文字 'x' があるため -> False
]
for test in test_cases:
result = DFA(test)
print(f"文字列: '{test:<8}' -> 受理結果: {result}")
では、if文によってδ関数を代用してましたが、
δ関数を辞書化によって、見やすくするとどうなるでしょうか。
＜辞書でδ関数を実装する＞
# --- 辞書によるDFAの定義 ---
# 状態集合 Q
states = {'q_even', 'q_odd', 'q_err'}
# アルファベット Σ
alphabet = {'a', 'b', 'c', 'd'}
# 初期状態 q0
start_state = 'q_even'
# 受理状態集合 F
accept_states = {'q_even'}
# 遷移関数 δ: (状態, 文字) -> 次の状態
# ※ 定義外の文字やエラー状態からの遷移は get() のデフォルト値で処理
delta = {
('q_even', 'a'): 'q_odd',
('q_even', 'b'): 'q_even',
('q_even', 'c'): 'q_even',
('q_even', 'd'): 'q_even',
('q_odd', 'a'): 'q_even',
('q_odd', 'b'): 'q_odd',
('q_odd', 'c'): 'q_odd',
('q_odd', 'd'): 'q_odd',
}
def dfa_dict(target_string):
current_state = start_state
for char in target_string:
# 辞書から次の状態を取得（未定義の文字が来たら 'q_err' へ移行）
current_state = delta.get((current_state, char), 'q_err')
# エラー状態に入ったらその時点で処理を中断（トラップ状態）
if current_state == 'q_err':
return False
# 最終状態が受理状態集合 F に含まれるか判定
return current_state in accept_states
# --- テスト実行 ---
test_cases = [
"", # aは0個 (偶数) -> True
"bcd", # aは0個 (偶数) -> True
"ab", # aは1個 (奇数) -> False
"aba", # aは2個 (偶数) -> True
"aacaada", # aは4個 (偶数) -> True
"abcdaaaa", # aは5個 (奇数) -> False
"abx" # 定義外の文字 'x' があるため -> False
]
for test in test_cases:
result = dfa_dict(test)
print(f"文字列: '{test:<8}' -> 受理結果: {result}")
＜振り返り＞
課題では正規表現を使わずにということですが、正規表現＝有限オートマトンだから、
オートマトンでかけるならば、正規表現でもコードが作れますね。
import re
# 正規表現パターンの定義
# ^ : 先頭
# [bcd]* : 最初の 'a' が出るまでの 'b','c','d' (0個以上)
# (?: ... )* : 非キャプチャグループの繰り返し
# a[bcd]* : 1個目の 'a' と、その後の 'b','c','d'
# a[bcd]* : 2個目の 'a' と、その後の 'b','c','d' (これで 'a' が偶数個ペアになる)
# $ : 末尾
pattern = re.compile(r"^[bcd]*(?:a[bcd]*a[bcd]*)*{{SSR}}quot;)
def dfa_re(target_string):
# パターンに完全マッチするかどうかを判定
return bool(pattern.match(target_string))
# --- テスト実行 ---
test_cases = [
"", # aは0個 (偶数) -> True
"bcd", # aは0個 (偶数) -> True
"ab", # aは1個 (奇数) -> False
"aba", # aは2個 (偶数) -> True
"aacaada", # aは4個 (偶数) -> True
"abcdaaaa", # aは5個 (奇数) -> False
"abx" # 定義外の文字 'x' があるため -> False
]
for test in test_cases:
result = dfa_re(test)
print(f"文字列: '{test:<8}' -> 受理結果: {result}")
a,b,c,dの文字列でaが偶数なら受理するオートマトン
＜geogebra＞
"a" → -1（偶数・奇数の状態反転：1 ⇄ -1）
"b", "c", "d" → 1（状態維持：1 × 1 = 1, -1 × 1 = -1）
その他 → 0（エラー状態への遷移：何をやっても 0）
このように文字を数値に置き換えることで、文字読み取りが代数演算に置き換わります。
さらに、演算結果を状態を表す点の位置として表示します。
この「代数的な演算」がそのまま「オートマトンの状態遷移」になりますよ。
「0をかけたら二度と抜け出せない（トラップ状態）」
というDFAのエラー特性を、数値の積 Product(k) で表現します。
安定して動かすために、動いた結果をTakeでコマ切れにして作り、
それをProductによって、累積効果を先に計算しておきます。
スライダーによって読み取り位置を後付けで追いかけると、
スライダーで1文字ずつ入力を読み取っているような振る舞いが
表示でますね。
#数式ビューに次の内容を1行ずつコピペします。#は設定
S_e=(1,0) # 偶数状態（緑）
S_o=(-1,0) # 奇数状態（黄土）
Serr=(0,0) # エラー状態（赤）
InputChar="abcdefa"
InputBox(InputChar)
Le=Length(InputChar)
digit=Sequence(If(Element(InputChar, k) ≟ "a", -1, If(Element(InputChar, k) ≟ "b" ∨ Element(InputChar, k) ≟ "c" ∨ Element(InputChar, k) ≟ "d", 1, 0)), k, 1, Le)
sub=Sequence(Take(digit,1,k),k,1,Le)
Ps=Zip(Product(k),k,sub)
P0=Join({{1},Ps})
Num=Slider(1,Le+1,1) #設定＞上級＞アニメーション＞モード＞増加（1回）
pos=Element(P0,Num)
dispChar="_"+InputChar
P=(pos,0) # 現在の状態を示す動点（青・サイズ最大）
poschar=Element(dispChar,Num)
a=Num-1
text=""+a+"文字目"+poschar+""
#操作の仕方
0文字目は開始前の状態を表します。
入力ボックス1の"abcdefaa"を適当に変えましょう。
Numを手動で１に戻します。
Numのプレイボタンを押すと、オートマトンに1文字ずつ
データが入り、Pが今の状態になります。
S_eがaが偶数個状態
S_oがaが奇数個状態
Serrが｛a,b,c,d｝以外の文字の入力によるエラー
Numがとまると判定がPの位置でわかります。
PがS_eで受理されますね。
タイトルは「a,b,c,dの文字列でaが偶数なら受理するオートマトン」
一度エラーになると、aが偶数個でもエラーになりますね。
これは、0を入れた積が0になることが効いてます。