推导的定义 若存在v=wo→w1→…→wn=w,(m>0) 则记为v=+w,称作v推导出w,或w归约 到 若有ⅴ=+w或v=w,则记为v=>*w
11 推导的定义 若存在v =w0 w1 ... wn =w,(n>0) 则记为v =>+ w，称作v推导出w，或w归约 到v 若有v =>+ w 或 v=w， 则记为v =>* w
例:G:S→0S1,S→01 0sS1=00S11 00S11→000s111 000S111→0000111l S→0S1→00S11→000S111→00001111 S=>+00001111 5=*S00s11>*00s11 12
12 例：G： S→0S1， S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =>+ 00001111 S =>* S 00S11 =>* 00S11
句型、句子的定义 8句型 有文法G,若S→*x,则称x是文法G的句型。 8句子 有文法G,若S→*x,且x∈V*,则称x是文法G的句子。 例:G:S→051,S→01 S→0S1→00s11→000S111→00001111 G的句型S0S1,00S11,00011000011 G的句子000011,01
13 句型、句子的定义 z句型 有文法G，若S =>* x，则称x是文法G的句型。 z句子 有文法G，若S =>* x，且x∈VT * ，则称x是文法G的句子。 例：G： S→0S1， S→01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01
句型、句子 例:G[E]:E→E+TT T→T*FF F→(E)|a E→E+T→T+T→F+T→a+T→a+T*F →a+FF→a+aF→a+a*a 句子:用符号a,+,*,(和)构成的算术表达式
14 句型、句子 例：G[E]： E→E+T|T T→T*F|F F→(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+， * ，(和)构成的算术表达式
(文法生成的语言的定义 由文法G生成的语言记为LG)它是文法G的 切句子的集合: L(G)={x|S=*x,其中S为文法的开始 符号,且x∈Vn 例:G:S→0s1,S→01 L(G)={0n1叫n≥1} 15
15 (文法生成的)语言的定义 由文法G生成的语言记为L(G),它是文法G的 一切句子的集合: L(G)={x|S =>* x，其中S为文法的开始 符号，且x ∈VT *} 例：G： S→0S1， S→01 L(G)={0n1n|n≥1}