2.正規言語とオートマトンの等価性
1
モデル間の関係
モデルの言語表現能力を評価する。
モデルAが与えられたとき、同じ言語を受理するモデルBが
作れるときモデルBの方が言語記述能力が高い(低くはない)。
これを、A→Bとアークを引いて表す。
例えば、DFAの記述は、ほとんどその定義のまま、
NFAの記述になる。したがって、
NFA
GNFA
DFA
正規表現
(RE)
2
目標
これらのモデルがすべて同じ言語記述能力があることを
示したい。そのため、
下記のような関係を導いていく。
NFA
GNFA
DFA
RE
3
DFAからNFAへ
DFA
NFA
直感的には、明らかだが、ここでは、
形式的に示す。
任意のDFAを D  (Q, ,  , q0 , F ) とする。
このとき、 D と同じ言語を受理するNFA
N  (Q ', ,  ', q0 ', F ') を構成する。
1. Q '  Q, q0 '  q0 , F '  F
とする。
2. (qx )  qy のとき、  '(qx )  {qy }とする。
4
例
D  ({q1 , q2},{0,1},  , q1 ,{q2})
0
D
1

0
1
q1
q1
q2
q2
q1
q2
1
q1
q2
0
N  ({q1, q2},{0,1},  ', q1,{q2})
0
N
q1
1
1
'
q1
q2
0
q1
q1
1
q2 
q2 
q2
0
5
NFAからDFAへ
NFA
DFA
任意のNFAを N  (Q, ,  , q0 , F ) とする。
このとき、 N と同じ言語を受理するDFA
D  (Q ', ,  ', q0 ', F ') を構成する。
1.
Q ' q P (Q) とする。
(NFAの状態のべき集合で、DFAの状態を作る。)
2.
q0 '  {q0} とする。
6
3.F '
 {NFAの受理状態を 含むよ う な状態}
 {q  Q ' | q  F  }
4.
 '(q, s )
 {qのいずれかの状態から
s  で遷移する 状態}
{ ( r , s )}

rq
7
例   {a, b} とする。
NFA
N  {q0 , q1, q2}, ,  , q0 ,{q0}

q0
q1
q2
a
b

{q1 , q2 }
{q1 , q2 } {q2 }
{q0 }

q0
b
N
a
b
q1
a, b
a
q2
このNと同じ言語を受理するDFA
D  Q ', ,  ', q0 ',{q0}, F '
を作成する。
8
1. Q '  P (Q)
 ,{q0 },{q1},{q2 },{q0 , q1},{q0 , q2 }, 


{
q
,
q
},{
q
,
q
,
q
}
0
1
2
 1 2


{q0 , q1}
{q0 }
{q1}
{q0 , q2}
{q1 , q2 }
{q2 }
{q0 , q1 , q2 }
9
2.
3.
q0 '  {q0}
F '  q  Q ' | q  F  

{q0 , q1}
{q0 }
{q1}
{q0 , q2}
{q1 , q2 }
{q2 }
{q0 , q1 , q2 }
10
 (r, s)
4.  '(q, s) 
rq

q0
q1
q2
a
b

{q1 , q2 }
{q1 , q2 } {q2 }
{q0 }

'

a
b



{q0 }
{q1}
{q1 , q2 }
{q1 , q2 }
{q2 }
{q2 }
{q0 }

{q0 , q1}
{q0 , q2 }
{q1 , q2 }
{q0 }
{q1 , q2 }
{q1 , q2 }
{q1 , q2 }
{q0 , q1 , q2 }
{q2 }
{q0 , q1 , q2 } {q0 , q1 , q2 } {q1, q2 }
11
a, b
b
a

a
{q0 }
a
{q0 , q1}
b
{q1}
b
a
b
b
b
{q0 , q1 , q2 }
{q1 , q2 }
{q0 , q2}
{q2 }
a
a
a, b
12
練習   {a, b}
NFA
とする。
N  {q0 , q1, q2}, ,  , q0 ,{q1}

q0
q1
q2
a
b
{q1}
{q1}
{q1 , q2 }

{q0 } {q1 , q2 }
q0
a
a, b
N
a
q1
b
a
q2
b
このNと同じ言語を受理するDFA
D  Q ', ,  ', q0 ',{q0}, F '
を構成せよ。
13
補足
初期状態から、到達可能でない状態はDFAから削除できる。
a, b
b
a

a
{q2 }
{q0 }
b
b
b
{q0 , q1 , q2 }
{q1 , q2 }
a
a
14
NFA→DFAの証明
x の長さ x に関する帰納法で
 '(q0 ', x)  {q1, q2 , , qi }
文字列
であるための必要十分条件が、
 (q0 , x)  {q1, q2 , , qi }
であることを示す。
基礎
x 0
x 
q0 '  {q0}
このとき、
であり、しかも
である。
よって、明らかに成り立つ。
15
帰納
x  m のとき成り立つと仮定する。
長さが m  1 の文字列 xs ( s  
 '(q0 ', xs)   '( '(q0 ', x), s)
)に対して、
を考える。
帰納法の仮定より、
 '(q0 ', x)  { p1 , p2 , , p j }
  (q0 , x)  { p1 , p2 ,
, p j}
また、  ' の定義から、
 '({ p1 , p2 , , p j }, s)  {r1 , r2 , , rk }
  ({ p1 , p2 ,
, p j }, s)  {r1 , r2 ,
, rk }
16
よって、
 '(q0 ', xs)  {r1 , r2 , , rk }
  (q0 , xs)  {r1 , r2 , , rk }
また、
 '(q0 ', x)  F '   (q0 , x)  F  
である。
したがって、
L( D)  L( N )
である。
QED
17
NFAから拡張NFAへ
GNFA
NFA
NFAの受理状態が複数あるのに対して、
GNFAの受理状態は一つである。
0
q000
0
0
q100
1 0 1
1
q001
0
0
q010
0 1
q011
q101
1
1

q110
0
q000
0
q001
q111
0
q100
1 0 1
1
0
0
qs


0 1
q011
q101
1
1
1
q010
1
q110
0
0
q111
1

qa

NFA
拡張NFA
18
1
ここでは、NFA→GNFAを形式的に示す。
任意のNFAを N  (Q, ,  , q0 , F ) とする。
このとき、 N と同じ言語を受理するGNFA
G  (Q ', ,  ', qs , qa ) を構成する。
1. 状態の追加
Q '  Q {qs , qa }
19
2.状態遷移関数 ' の決定
・通常の状態
q  Q, s  に対して、
 (q, s)  P  {qx | qxはqから 遷移可能な関数}
のとき、
q  Q ' {qs , qa }, s  に対して、 '(q, qx )  s
・初期状態
 '(qs , q0 )  
・受理状態
q  F に対して、
 '(q, qa )  
・上で定められていない定義域
 '(q, q ')  
20
練習
S = {a, b} とする。
次のNFAに対して、同じ言語を受理するGNFAを
状態遷移図と形式的定義の両方で与えよ。
q0
a
a, b
a b b
q2
q1
a
21
正規表現からGNFAへ
GNFA
RE
方針:
任意の正規表現 r に対して、
L(r ) = L(G )
となるような
G = (Q, S , d, qs , qt )
を構成する。
正規表現に基づいて、再帰的に構成していく。
22
演算数による帰納法
アルファベットを
とする。
S
基礎
r= f
Gf
r= e
Ge
のとき、
qs
qt
のとき、
qt
r = a(Î S )
qs
a
qt
23
帰納
演算数が m 以下のどんな正規表現r ' も
対応するGNFAがあるとする。
演算数が m
+ 1 である正規表現 r
を考える。
正規表現の定義より、3つの場合が存在すr。
(1)場合1
r = r1 + r2 の形にできるとき。
ここで、 r1, r2 は、正規表現だが、
演算数は m 以下である。
よって、
L(r1 ) = L(G1 ), L(r2 ) = L(G 2 )
となる2つのGNFA
G1,G 2 が存在する。
24
これらを用いて L (r ) を受理するGNFA G を
以下のように構成できる。
e
q
1
s
G1
q
1
t
e
qt
qs
e
qs2
G2
qt2
e
G
25
(2)場合2
r = r1r2
の形にできるとき。
ここで、 r1, r2 は、正規表現だが、
演算数は m 以下である。
よって、
L(r1 ) = L(G1 ), L(r2 ) = L(G 2 )
となる2つのGNFA
G1,G 2 が存在する。
これらを用いて L (r ) を受理するGNFA G を
以下のように構成できる。
1
s
q
qs
G1 q
1
t
e
2
s
2
G
q
2 qt
qt
G
26
(3)場合3
*
1
r= r
の形にできるとき。
ここで、 r1
は、正規表現だが、
演算数は m 以下である。
よって、 L (r ) = L (G ) なるGNFA
1
1
G 1 が存在する。
これらを用いて L (r ) を受理するGNFA G を
以下のように構成できる。
e
qs
e
qs1 G 1 qt1
e
qt
e
G
27
以上より、
任意の正規表現はGNFAに変換可能である。
QED
28
例 S = {0,1}
*
上の正規表現 r = 01 + 1 を受理する
GNFA G を構成する。
r1 = 01*, r2 = 1 とおけば、 r = r1 + r2
r3 = 0, r4 = 1*
r5 = 1
である。
とおけば、 r1 = r3r4
である。
r4 = r5*
である。
とおけば、
よって、まず基礎が以下のように構成できる。
G5
qs5
G3
3
s
G2
q
2
s
q
1
0
1
qt5
qt3
qt2
29
r4 = r5*
を受理するGNFA G 4
e
4
s
q
5
s
q
は、 G 5を用いて
e5
1
qt
e qs4
G5 e
G4
r1 = r3r4
3
s
q
G1
を受理するGNFA G 1
0
3
t
q
は、 G 4を用いて
e q e qs5
4
s
1
e
5
t
q
e qs4
e
G3
G4
30
r = r1 + r2
3
s
q
0
は、 G 1を用いて
を受理するGNFA G
3
t
q
e qs4 e qs5
1
e
5
t
q
e qs4
e
e
G1
e
qs
qt
e
2
s
q
1
2
t
q
e
G2
31
練習
S = {0,1}
*
r
=
(10
+
0)
上の正規表現
を受理する
GNFA G を構成せよ。
32
GNFAから正規表現へ
RE
GNFA
方針:
任意のGNFA
G = (Q, S , d, qs , qt ) に対して、
L(G ) = L(r )
となるような
r
を導く。
Gの状態数を減少させることにより、
最終的には2状態のGNFAを構成していく。
33
状態の削除法
1.削除する状態 q p  Q を決める。
2.すべての組 qi , q j  Q  {qp } に対して,
次のようなアークを構成する。
qi
rij
qj
rip
qp
qi
rij  r r r
*
ip pp pj
qj
rpj
rpp
削除前
削除後
34
例
0
q0
e
qs
GNFAへ
1
q1
q0
1
qt
1, 0
0
e
q1
q1削除
1, 0
0
qs
e
0
qs
q0
  1(1  0) 
*
 1(1  0)*
0*1(1  0)*
q2削除
qt
qt
35
例2
q0
0
1 0
1
1
q1
qs
1
11
q1
q2 0  10
e
1  00
1
q1
0
q2
0
01
0
1 0
1
q0 削除 、複数のアーク
を生成することに注意。
qs
q0
GNFAへ
0
q2
e
e
e
qt
q1
削除
e
qt
36
qs
0(1  00)*
qt
1  0(1  00)* 01
  (0  10)(1  00)*
q2
11  (0  10)(1  00)* 01
q2
削除
0(1  00)* 
qs
(1  0(1  00)* 01)(11  (0  10)(1  00)* 01)* (  (0  10)(1  00)* )
qt
37
練習
次のDFAが受理する言語を正規表現で示せ。
q0
0
0
1
q1
q2 0,1
1
38
2-2. 正規言語の性質
ここでは、DFAの限界を示す。
実際、次のような言語は、正規言語ではない。
B = {0 1 | n ³ 0}
n n
C = {w | wは0 と 1 を同じ 数だけ含む文字列}
正規言語でないことを示すための、有用な補題(定理)がある。
39
ポンピング補題
ポンピング補題
Aが正規言語であるならば、ある数 p (ポンピング長)が
存在して、 p より長い任意の文字列 s Î A に対して、
次を満たすように s を
s = xyz
に分割できる。
1.各 i ³ 0 について、 xy i z Î A
2. y ³ 1,(y ¹ e)
3. xy £ p
40
ポンピング補題の意味
正規言語 A を認識するDFAを M A = (Q, S , d, q0, F )
とする。
実は、 p を M A の状態数( p = | Q | )とすると補題が成り立つ。
入力が状態数を超えているとき、必ず状態遷移中に
2度以上おとづれる状態が存在しているはずである。
(このことは、鳩ノ巣原理と呼ばれます。)
例えば、 s = s1s 2s 3s 4 L sn Î A による M A の
状態遷移が q0q3q5q1q4q5 L q10 であったとする。
ここで、 q10 Î F としています。
41
例の状態遷移
q0
s1
q3
s2
q5
s3
q1
s4
q4
s5
q5
s6
sn
同じ状態
この例では、
x = s1s 2 y = s 3s 4s 5 z = s 6 L s n
i
xy
zÎ A
とすればよい。このとき、
x
q0
q5
である。
y
z
q10
42
q10
ポンピング補題の証明
正規言語 A を認識するDFAを
p = | Q | とする。
また、 n
³ p
とし、
M A = (Q, S , d, q0, F )
s = s1s2s 3s 4 L sn Î A
とし、
とする。
s
を入力としたときの、 M A の状態遷移の系列を
r1r2 L rn + 1とする。すなわち、 1 £ i £ n に対して、
ri + 1 = d(ri , si )
である。
鳩ノ巣原理より、列 r1r2 L rn + 1 の最初の p + 1 個の中に
同じ状態が2回以上現れる。
2回現れた状態の一回目を r j とし、
2回目を rk とする。
43
ここで、
x = s1 L s j - 1
y = s j L sk - 1
z = sk L sn
とおく。
このとき、補題の3条件をすべて満たしている。
QED
44
非正規な言語
次の言語は正規言語ではない。
B = {0n 1n | n ³ 0}
B = {w | wは0 の列のあと に同じ 長さ の1 の列が続く }
= {e, 01, 0011, 000111, 000011111, L }
45
証明
ポンピング補題を用いて背理法で証明する。
Bは正規言語であると仮定する。(背理法の仮定)
Bは正規言語であるので、あるポンプ長 p が存在する。
s = 0 p1p とする。
このとき、ポンピング補題より、
s = xyz
と分割できる。
このとき、 y として次の3つの場合が考えられる。
(1)0だけ
(2)1だけ
(3)0の列と1の列の連結
しかし、次のようにいずれの場合も矛盾が生じる。
46
(1) y が0だけのとき
このとき、ポンピング補題より、
xy 2z = xyyz も B に含まれなければならない。
( xyyz Î B )
しかし、 xyyz は0の数が多いので xyyz Ï B であり、
矛盾が生じる。
(2) y が1だけのとき
(1)と同様に矛盾が導ける。
(3) y が0の列と1の列の連結のとき
y = 0j 1k とする。
j k j k
このとき、 xyyz = x 0 1 0 1 z であるが、
1の前に0があり xyyz Ï B である。
以上、すべての場合で矛盾が生じるので、
Bは正規言語ではない。
QED
47
ダウンロード

ppt