33语言与文法简介 ⑦正规式与上下文无关文法 1.正规式到CFG的转换 推论3.1正规式描述的语言结构均可用CFG描述,反之不一定 从正规式到CFG的对应关系: ①构造正规式的NFA; ②若0为初态,则AO为开始符号; ③对于move(ia),引入产生式Ai→aAj; 经验的方法: ④对于move(i;l),引入产生式Ai→Aj; A→HT ⑤若是终态,则引入产生式Ai→E。 H→E|HaHb [例3.1从正规式=ab)*ab的NFA构造CFG:T→ab A0→aAO| bANaL A1→bA2 b b 0 A2→bA3 A3→￡10 3.3 语言与文法简介  正规式与上下文无关文法 1. 正规式到CFG的转换 推论3.1 正规式描述的语言结构均可用CFG描述，反之不一定 从正规式到CFG的对应关系： ① 构造正规式的NFA； ② 若0为初态，则A0为开始符号； ③ 对于move(i,a)=j，引入产生式Ai→aAj； ④ 对于move(i,ε)=j，引入产生式 Ai→Aj； ⑤ 若i是终态，则引入产生式Ai →ε。 [例3.11] 从正规式r=(a|b)*abb的NFA构造CFG： A0 → aA0|bA0|aA1 A1 → bA2 A2 → bA3 A3 → ε 经验的方法： A → HT H →ε| Ha | Hb T → abb 0 1 2 3 a b b a b