４．プッシュダウンオートマトンと 　　文脈自由文法の等価性

内容

1. スライド　1 ４．プッシュダウンオートマトンと　　文脈自由文法の等価性
2. スライド　2 ４−1．目標
3. スライド　3 CLG→PDAのアイディア
4. スライド　4 このとき、次のように動作するPDAを構成すればよい。
5. スライド　5 スタックの拡張
6. スライド　6 PDA
7. スライド　7 状態遷移関数　　は次のように定める。
8. スライド　8 スライド8
9. スライド　9 例
10. スライド　10 （拡張スタックを用いた）等価なＰＤＡ
11. スライド　11 １文字スタックへの変換
12. スライド　12 練習
13. スライド　13 PDA→CFGのアイディア
14. スライド　14 PDAからCFGの構成
15. スライド　15 ４．規則の設定
16. スライド　16 （2）
17. スライド　17 イメージ１
18. スライド　18 イメージ２
19. スライド　19 例
20. スライド　20 のとき、
21. スライド　21 （２）
22. スライド　22 練習
23. スライド　23 正規言語（RL)と文脈自由言語（CFL)
24. スライド　24 （CFLの）ポンピング補題
25. スライド　25 ポンピング補題の意味
26. スライド　26 構文解析木の葉から開始記号までの道上に 同じ非終端記号が現れたとき、 下のよ...
27. スライド　27 スライド27
28. スライド　28 ポンピング補題の証明
29. スライド　29 　　を少なくとも長さ　　であるAの文字列とする。 このとき　　を生成する構文解...
30. スライド　30 CFLの限界
31. スライド　31 証明
32. スライド　32 このとき、次の２つの場合に分けて考える。 （１）　　　と　　　はどちらも1種類...