PowerPoint プレゼンテーション

空動作のある非決定性有限オートマトン
M  Q, , , q0 , F 
Q
状態の有限集合

入力記号の有限集合
注意
 : Q  ( { })  2

動作関数
q0
初期状態
F
受理状態の有限集合
Q
q0  Q
F Q
空動作のある非決定性有限オートマトン
M 23  Q, ,  , q0 , F 
Q  { p, q, r}
  {0,1}
 : Q  ( { })  2
Q
 ( p,  )  {q, r},  ( p,0)   ( p,1)   ,
 (q,0)  {q},
 (q,1)   (q,  )   ,
 (r ,1)  {r},
 (r ,0)   (r ,  )  
q0  p
F  {q, r}
M 23の状態遷移図
pp
{,qq,,rr}}
QqF

{

0
0

p
q
 (p((q,r,10))){{{qrq,}}r}

r
1
 (q
( p,,10))
 (q,  )  
 ((rp,,01)) 


 (r ,  )  
入力語00に対する M 23の動作
0
0
0 $

p
q

r
1
0
場合１
0 $

p
0
q

r
 ( p,0)  
 ( p,  )  {q, r}
場合２
２通りの可能性あり。
1
場合１
0
0
0 $

p
q

r
1
 (q,0)  {q}
0
0
0 $

p
q

r
1
 (q,0)  {q}
0
0
0 $

p
q

r
1
入力語を読み終えて，受理状態に遷移した。
場合２
0
0
0 $

p
q

r
1
 (r ,0)  
これ以上，遷移できない。
よって，入力語 00 に対して２つの遷移の可能性があるが，
0
0
0 $

p
q

r
1
0
0
0 $

p
q

r
1
0
0
0 $

p
q

r
1
0
0
0 $

p
q

r
1
入力語を読み終えたとき受理状態に到達する
遷移が可能なので，入力語 00 は受理される。
入力語111に対する M 23の動作
1
1
0
1 $

p
q

r
1
同様に，
入力語を読み終えたとき受理状態に到達する遷移
が可能なので，入力語 111 は受理される。
入力語110に対する M 23の動作
1
1
0
0 $

p
q

r
1
入力語を読み終えることができないので，
入力語 110 は拒否される。
0

p
q

r
1
なお，
L(M 23 )  {w | wは 0または 1のみからなる語 } { }
である。

Download Report