PowerPoint プレゼンテーション

決定性PDAと非決定性PDA
形式言語とオートマトン：第7回講義
dpda M 33  Q, , ,  , q0 , Z0 , F 
Q  {q0 , q1 , q2}
  {0,1, # }
  { A, B, Z 0 }
 : Q  ( { })  の部分集合  Q  *
 (q0 ,0, Z 0 )  (q0 , AZ0 ), (q0 ,1, Z 0 )  (q0 , BZ0 ),
 (q0 ,0, A)  (q0 , AA), (q0 ,0, B )  (q0 , AB),
 (q0 ,1, A)  (q0 , BA), (q0 ,1, B )  (q0 , BB),
 (q0 , # , A)  (q1 , A), (q0 , # , B )  (q1 , B ),
 (q1 ,0, A)  (q1 ,  ), (q1 ,1, B )  (q1 ,  ),
 (q1 ,  , Z 0 )  (q2 , Z 0 )
F  {q2 }
M 33の状態遷移図
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
# , A/ A
#, B / B
q1
 , Z0 / Z0
q2
M 33の動作例
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A A B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A A B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
B A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0 1 0 0 # 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
受理条件を満た
す様相に到達す
ることができた。
# , A/ A
#, B / B
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
# , A/ A
#, B / B
q1
 , Z0 / Z0
q2
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
なお，

L(M33 )  {w# w | w {0,1} }
R
である。
非決定性PDAで判別できる入力
• 真ん中に#を入れない場合でも、nPDAなら
判別できる
• これはdPDAにはない能力である
npda M 34  Q, , ,  , q0 , Z0 , F 
Q  {q0 , q1 , q2}
  {0,1}
  { A, B, Z 0 }
 : Q  ( { })  の部分集合  2
Q*
 (q0 ,0, Z 0 )  {( q0 , AZ0 )}, (q0 ,1, Z 0 )  {( q0 , BZ0 )},
 (q0 ,0, A)  {( q0 , AA), (q1 ,  )}, (q0 ,0, B)  {( q0 , AB)},
 (q0 ,1, A)  {( q0 , BA)}, (q0 ,1, B )  {( q0 , BB), (q1 ,  )},
 (q1 ,0, A)  {( q1 ,  )}, (q1 ,1, B )  {( q1 ,  )},
 (q1 ,  , Z 0 )  {( q2 , Z 0 )}
F  {q2 }
M 34の状態遷移図
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
0, A / 
1, B / 
q1
 , Z0 / Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
M 34の動作例
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
A
Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
B A Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
A B
 , Z0 / Z0
q2
２通りの遷移の可能性が
あるが，ここではこちらの
遷移を選ぶ。
A Z0
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
q2
ここでも２通りの遷移の
可能性があるが，今度は
こちらの遷移を選ぶ。
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
A
A B
A Z0
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
A B
A Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
B A Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
A Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
Z0
q2
0 1 0 0 0 0 1 0 $
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
受理条件を満た
す様相に到達す
ることができた。
0, A / 
1, B / 
q1
 , Z0 / Z0
0, A/ AA
0, B / AB
1, A / BA
1, B / BB
Z0
q2
0, A / 
1, B / 
0, Z0 / AZ0
1, Z0 / BZ0
q0
0, A / 
1, B / 
q1
 , Z0 / Z0
q2
0, A/ AA
0, B / AB
1, A/ BA
1, B / BB
なお，

L(M 34 )  {ww | w {0,1} }
R
である。

Download Report