计算理论03_CFL研究.pptVIP

第三讲课程 用前后文相关(CSL) 的来反衬托CFL直观概念 前后文无关的直观概念 Context-Free Languages (Ch. 2)前后文无关语言 Context-Free Languages (Ch. 2)前后文无关语言 Context-Free Grammars (Inf.)前后文无关文法 与ep92 例类似，但稍简单 Context-Free Grammars (Def.2.1) ep94 Context-Free Grammars (Def.2.1) ep94 Derivation ?* 派生，生成， ep94, cp61 Derivation ?* 派生，生成， ep94, cp61 Some Remarks ep94 cp61 Context-Free Grammars (Ex.) 例c3.2 稍有不同 ep95 , cp61 书上例子自学 Importance of CFL Example Boolean Algebra 补充例有两个字符，有与、或、非，刚好等价于 布尔代数 Example Boolean Algebra 补充例有两个字符，有与、或、非，刚好等价于 布尔代数 Human Languages ep93, cp60 Human Languages ep93, cp60 Human Languages ep93, cp60 Parse Trees ep 93，书上无此图，类似于cp62 Ambiguity ep97 cp63I saw that girl with telescope (人分辨时 要看前后文） Ambiguity and Parse Trees 与ep98 cp63 图稍微不同 思想一致 More on Ambiguity Context-Free Languages Def, ep99, cp60 Context-Free Languages Def, ep99, cp60 Context-Free Languages Def, ep99, cp60 “Chomsky Normal Form” 定义 c3.5 ep99 cp64 “Chomsky Normal Form” 定义 c3.5 ep99 cp64 Theorem c3.6 ep99 cp64 Theorem c3.6 ep99 cp64 Theorem c3.6 ep99 cp64 Proof Theorem c3.6 ep99 CFL ~ Chomsky NF ep99 ,cp64 Proof Theorem c3.6 ep99 CFL ~ Chomsky NF ep99 ,cp64 Careful Removing of Rules去掉冗余的规则 RL ? CFL 命题 : 正则语言是CFL RL ? CFL 命题 : 正则语言是CFL Example RL ? CFL 边 对应于 规则 Picture Thus Far Any Question ? Given a context-free grammar G = (V,?,R,S),rewrite it to Chomsky Normal Form by 1) New start symbol S0 (and add rule S0?S) 2) Remove A?? rules (from the tail): before: B?xAy and A??, after: B? xAy | xy 3) Remove unit rules A?B (by the head): “A?B”  and “B?xCy”, becomes “A?xCy” and “B?xCy” 4) Shorten all rules to two: before: “A?B1B2…Bk”,  after: A?B1A1, A1?B2A2,…, Ak-2?Bk-1Bk 一分为多 通过多个 一分为二 实现 5) Replace ill-placed terminals 1-2-3为核心的4作准备 S0?? A?ai A?BC A?aiB A?Bai A?aiaj add a variable Ui and rule Ui?ai,then d’) A?UiB e’) A?Bui f’) A?UiUj Every regular language can be expressed bya context-free grammar. Proof Idea: RL ?DFA?造CFG,