２．正規言語とオートマトンの等価性

内容

1. スライド　1 ２．正規言語とオートマトンの等価性
2. スライド　2 モデル間の関係
3. スライド　3 目標
4. スライド　4 DFAからNFAへ
5. スライド　5 例
6. スライド　6 NFAからDFAへ
7. スライド　7 3．
8. スライド　8 例
9. スライド　9 １．
10. スライド　10 2．
11. スライド　11 ４．
12. スライド　12 スライド12
13. スライド　13 練習
14. スライド　14 補足
15. スライド　15 NFA→DFAの証明
16. スライド　16 帰納
17. スライド　17 よって、
18. スライド　18 NFAから拡張NFAへ
19. スライド　19 ここでは、NFA→GNFAを形式的に示す。
20. スライド　20 ２．状態遷移関数　　の決定
21. スライド　21 練習
22. スライド　22 正規表現からGNFAへ
23. スライド　23 演算数による帰納法
24. スライド　24 帰納
25. スライド　25 これらを用いて　　　　　を受理するGNFA　　　を 以下のように構成できる。
26. スライド　26 （２）場合２ 　　　　　　　　　　　　の形にできるとき。
27. スライド　27 （３）場合３ 　　　　　　　　　　　　の形にできるとき。
28. スライド　28 以上より、 任意の正規表現はGNFAに変換可能である。
29. スライド　29 例
30. スライド　30 は、　　を用いて
31. スライド　31 は、　　を用いて
32. スライド　32 練習
33. スライド　33 GNFAから正規表現へ
34. スライド　34 状態の削除法
35. スライド　35 例
36. スライド　36 例２
37. スライド　37 削除
38. スライド　38 練習
39. スライド　39 ２−２．　正規言語の性質
40. スライド　40 ポンピング補題
41. スライド　41 ポンピング補題の意味
42. スライド　42 例の状態遷移
43. スライド　43 ポンピング補題の証明
44. スライド　44 ここで、
45. スライド　45 非正規な言語
46. スライド　46 証明
47. スライド　47 （１）　　が0だけのとき