PowerPoint プレゼンテーション - NIPPON INSTITUTE of

決定性プッシュダウンオートマトン
M  Q, , ,  , q0 , Z0 , F 
Q



状態の有限集合
 (q,  , Y ) が定義されているときは，
入力記号の有限集合
どの a に対しても，
 (q, a, Y ) は定義されていない。
プッシュダウン記号の有限集合
動作関数
（動作の決定性が保証される。）
 : Q  ( { })  の部分集合  Q  
*
q0
初期状態
q0  Q
Z0
ボトムマーカー
Z0  
F
受理状態の有限集合 F  Q
決定性プッシュダウンオートマトンの
１ステップの動作（１）
…
a
x
 (q, a, Y )  ( p,  )
有限制御部
q
状態
Y
$
のとき

Z0
…
a
x
$
有限制御部
状態
に遷移する。
p


Z0
決定性プッシュダウンオートマトンの
１ステップの動作（２）
…
a
x
 (q,  , Y )  ( p,  )
有限制御部
q
状態
Y
$
のとき

Z0
…
a
x
$
有限制御部
状態
に遷移する。
p


Z0
(q0 , a1a2a3...an , Z0 )
初期様相
a1 a2 a3
有限制御部
状態
q0
Z0
…
an
$
 (q0 , a1 , Z0 )  (q1 ,1Z0 )
(q1 , a2a3...an ,1Z0 )
次の様相
a1 a2 a3
…
有限制御部
状態
q1
1
Z0
an
$
以下，ステップを繰り返して，
動作停止時の様相
a1 a2 a3
…
(qn ,  ,  n Z 0 )
q n  F

 n  
an $
のとき，
有限制御部
状態
入力語を受理。
qn
n
Z0
M 31  Q, , ,  , q0 , Z0 , F 
Q  {q0 , q1 , q2}
  {a, b}
  {A, Z0 }
 : Q  ( { })  の部分集合  Q  *
 (q0 , a, Z 0 )  (q0 , AZ0 ),
 (q0 , a, A)  (q0 , AA),
 (q0 , b, A)  (q1 ,  ),
 (q1 , b, A)  (q1 ,  ),
 (q1 ,  , Z 0 )  (q2 , Z 0 )
F  {q2 }
M 31の状態遷移図
F
{1q,2q}2}
q0{
Q
q0q, 0q
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
 (q(0q,(aq
()
AZ
), q
b,A
,)A
)Z0(,q
q,0AA
) )2), Z0 )
,0qZa,(1b0,q,),A
,q
q0(1,
1(
0(
1
0()
q2
入力語aaabbbに対する M 31の動作
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A A Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
a a a b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
a a a b b b
a, Z0 / AZ0
入力語を読み終えたとき，
受理状態に遷移し,その時
プッシュダウンスタックは
空（ボトムマーカーのみ）
なので，M31 は入力語
aaabbb を受理する。
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
入力語aaabbに対する M 31の動作
a a a b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
a a a b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
a a a b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
a a a b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A A Z0
q2
a a a b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
入力語は読み終えた
が,受理状態ではなく,
プッシュダウンスタック
も空ではない。これ以
上遷移できないので
M31 は入力語 aaabb
を拒否する。
a a a b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
入力語aaabbbbに対する M 31の動作
a a a b b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
a a a b b b b
a, Z0 / AZ0
$
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
a a a b b b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
a a a b b b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A A Z0
q2
a a a b b b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A A Z0
q2
a a a b b b b $
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
A Z0
q2
a a a b b b b $
a, Z0 / AZ0
入力語を読み終えること
ができない（これ以上遷
移できない）ので，M31
は入力語 aaabbbb を拒
否する。
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
a, A / AA
Z0
q2
同様に,
・ M31 は，a だけから成る入力語は読み終
えることはできるが，読み終えて遷移する状
態は受理状態ではなく，かつその時のプッ
シュダウンスタックは空でない。
また，
・いくつかの a の後にいくつかの b が来て
さらに a が来るような入力語,
・ b から始まる入力語
は，いずれも M31 はその入力語を読み終え
ることができない。
a, Z0 / AZ0
b, A / 
q0
b, A / 
q1
 , Z0 / Z0
q2
a, A / AA
よって，
L(M 31 )  {a b | n  1}
n n
である。

Download Report