非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.

Presentation on theme: "非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合."— Presentation transcript:

1 非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合

2 非決定性有限オートマトン

3

4

5

6 場合１ 場合２ ２通りの可能性がある。

7 場合１ 場合１－１ 場合１－２ ここでまた２通りの可能性がある。

8 場合１－１

9 場合１－２

10 場合２

11

12 よって，入力語 baa に対して３つの遷移の可能性があるが，

13

14

15 入力語を読み終えたとき受理状態に到達する遷移が可能なので，入力語 baa は受理される。

16

17 場合１ 場合２ ２通りの可能性がある。

18 場合１ 場合１－１ 場合１－２ ここでまた２通りの可能性がある。

19 場合１－１

20

21 場合１－２ これ以上，遷移できない。

22 場合２

23 これ以上，遷移できない。

24 よって，入力語 aab に対して３つの遷移の可能性があるが，

25 第１の可能性は，

26

27

28 入力語を読み終えたとき受理状態に到達しない。

29 第２の可能性は，

30

31 これ以上遷移できない。

32 第３の可能性は，

33

34 これ以上遷移できない。

35 よって， いずれも，入力語を読み終えたとき受理状態に到達しないか，入力語を読み終えることができないので，入力語 aab は拒否される。

36 なお， である。