(2):文脈自由文法とPDA

Report
形式言語 と オートマトン
第14回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマトン
本日の予定
形式言語とオートマトン
試験の考察点(20%)
1.様相変化
2.PDAの7字組
形式言語とオートマトン
状態遷移図
様相?どういうこと?
形式言語とオートマトン
b
a
r
s
b
a
b
Dt
abbaを与えたときの一連
の動作を下記のように簡潔
に表す
a
(r,abba)
M
(s,bba)
M
(r,ba)
様相
形式言語とオートマトン
M
(r,a)
M
(s,ε)
b
a
r
s
b
最初と最後の様相だけに
関心があるときは
a
b
Dt
a
形式言語とオートマトン
(r,abba)
*
M
(s,ε)
b
a
r
s
b
a
b
最後に (終状態, 空列)となった
ら受理、そうでなければ受理しない
Dt
a
(r,abba)
M
(s,bba)
M
(r,ba)
M
(r,a)
M
(s,ε)
受理状態でない で終了
→拒否
形式言語とオートマトン
試験の考察点(20%)
1.様相変化
2.PDAの7字組
形式言語とオートマトン
状態遷移図
プッシュダウンオートマトンとは?
+
→ プッシュダウンオートマトン(PDA)
(FSAのような単純な装置では扱えない入力の判断を扱える)
試験
DPDA: deterministic pushdown automaton
NPDA: non- deterministic pushdown automaton
形式言語とオートマトン
記憶装置
ポップアップ
後入れ先出し(LIFO:Last-In First-Out)
方式の記憶装置
形式言語とオートマトン
決定性プッシュダウンオートマトン
7字組
M  Q ,  ,  ,  , q 0 , Z 0 , F 
Q
状態の有限集合

入力記号の有限集合

プッシュダウン記号の有限集合

動作関数
 : Q  (   { })   の部分集合
q0
Z0
F
初期状態
ボトムマーカー
受理状態の有限集合
 Q
q0  Q
Z0  
F Q
*
様相の書き方
…
x
a
$
この状態の様相は:
有限制御部
( q,ax,Y  Z 0 )
q
状態
Y
形式言語とオートマトン

Z0
1ステップの動作と様相の書き方
…
x
a
有限制御部
状態
p

形式言語とオートマトン
$
 (q, a, Y )  ( p, Y )
( q,ax,Y  Z 0 )

Z0
M(
p,x,  Y  Z 0 )
受理条件
(qn ,  , n Z 0 )
動作停止時の様相
a1 a 2 a 3
…
an
$
qn  F

 n  
入力  を受理する
有限制御部
( q 0 , a1 a 2 ... a n , Z 0 )
*M
状態
qn
(qn ,  , n Z 0 )
n
形式言語とオートマトン
Z0
例題
問1:下図の様相を示してください
…
y
b
有限制御部
状態
形式言語とオートマトン
q
(, )
$
例題
(, , 0 )
問2:下図の様相を示してください
…
y
b
$
有限制御部
状態 q
m
形式言語とオートマトン

Z0
問3:次の7字組で表されるDPDAに、入力aabbbbを読み込ませた場
合、様相変化を示せ。受理するかを示すこと
M  Q ,  ,  ,  , q 0 , Z 0 , F 
Q  { q 0 , q1 , q 2 }
  { a , b}
  { A, Z 0 }
 : Q  (   { })   の部分集合
 ( q 0 , a , Z 0 )  ( q 0 , AAZ 0 ),
 ( q 0 , a , A )  ( q 0 , AAA ),
 ( q 0 , b , A )  ( q 1 ,  ),
 ( q 1 , b , A )  ( q 1 ,  ),
 ( q1 ,  , Z 0 )  ( q 2 , Z 0 )
F  {q 2 }
 Q
*
問3のAnswer
( q 0 , aabbbb , Z 0 )
M ( q 0 , abbbb
M
( q1 , bbb , AAAZ 0 )
M
( q1 ,  , Z 0 )
, AAZ 0 )
M ( q1 , bb ,
AAZ 0 )
M
( q 0 , bbbb , AAAAZ
M
( q1 , b , AZ 0 )
M (q2 ,  , Z 0 )
受理状態
読み終えた
空
よって,受理する
0 を忘れずに,最後にを忘れずに!!!
形式言語とオートマトン
0
)
本日の予定
形式言語とオートマトン
1.言語の階層構造:言語とオートマトンの対応関係など
例
L  { a b | 1 ≦ m ≦ n ≦ 2 m }
m
n
は文脈自由言語に属し,文脈自由文法で生成でき,
プッシュダウン オートマトンで識別できる.
形式言語とオートマトン
正規表現
2.有限状態オートマトン
例:
a
b
ε
c
c
D
図示のNFAが受理する言語の正規表現を求めてください
a*b*cc*
形式言語とオートマトン
3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木)
文法G=<V,T,P,S>, V={A}, T={a,b}, P={A→aAb, A→AA, A→ab},
S={A}によって、abaabb という語が導出される過程はどのようになる
か、空白を埋めよ
A ⇒
AA
⇒
AaAb ⇒ abaAb ⇒
abaabb
これと同じ言語を生成する上のGと同等で文法G’をChomsky標準形
といい、G’=<V’,T’,P’,S’>を構成し、abaabbの導出木を作れ
形式言語とオートマトン
G’=<V’,T’,P’,S’> abaabbの導出木は:
S
V’={S,A,B,C},
A
T’={a,b},
P'  {S  AA, A  BC,
B
A
C B
C
C  AC, B  a, C  b}
A C
S’={S}
B
a
形式言語とオートマトン
ba a
C
b b
4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2
例:
a
b
ε
c
c
図示のNFAと同等なDFAの状態遷移図を描け.
形式言語とオートマトン
D
ANSWER
c
{D2 }
a
c
a,b
c
a,b,c
{0 , 1 }
b
a
{1 }
b
形式言語とオートマトン
Φ
5.状態遷移図
5字組及び状態遷移表の書き方
例1:
a
b
ε
c
c
D
図示のNFAと同等なDFAを5字組で表せ.また、NFAとDFAの状
態遷移表を描け.
形式言語とオートマトン
図示のNFAと同等なDFAを5字組で表せ.また、NFAとDFAの状
態遷移表を描け.
M=<Q, Σ, δ, S, F>
Q={{q0, q1}, {q1}, {q2},  }, Σ={a,b,c}, S={q0, q1}, F={{q2}}
δ({q0, q1},a)= {q0, q1}, δ({q0, q1},b)= {q1},
δ({q0, q1},c)= {q2},
δ({q1},a)= ,
δ({q1},b)= {q1},
δ({q1},c)= {q2},
δ({q2},a)=  , δ({q2},b)=  , δ({q2},c)= {q2},
δ(  , a)=  , δ(  ,b)=  , δ(  ,c)= 
形式言語とオートマトン
図示のNFAと同等なDFAを5字組で表せ.また、NFAとDFAの状
態遷移表を描け.
NFA
a
b
0 {0 , 1 } {1 }
DFA
{2 }
1

{1 }
{2 }
2


{2 }
形式言語とオートマトン
a
c
b
{0 , 1 } {0 , 1 } {1 }
c
{2 }
{1 }

{1 }
{2 }
{2 }


{2 }




5.状態遷移図
5字組及び状態遷移表の書き方
例2:
正規表現b*a(a+b)*bbについてNFAとそれに同等な
DFAの状態遷移表と状態遷移図を作れ.
形式言語とオートマトン
正規表現b*a(a+b)*bbについてNFAとそれに同等な
DFAの状態遷移表と状態遷移図を作れ.
NFA
b
a
0
DFA
b
{q 0 }
状態遷移表(略)
a,b
1
b
2
b
D3
b
a
a
{q 1 }
b
a
{q 1 ,q 2 }
a
形式言語とオートマトン
b
{ q1 , q 2 , q 3 }
お疲れ様です!!
形式言語とオートマトン

similar documents