二.文法产生的语言 1推导与归约 ①直接推导:aβ→06v 即由产生式右边替换产生式左边 ②推导a1当an、a1→d ③归约推导的逆过程
二. 文法产生的语言 1. 推导与归约 ①直接推导: αβ α 即由产生式右边替换产生式左边 ②推导:α1 αn、α1 αn ③归约:推导的逆过程 * +
举例已知GF)E→E+EEE|(E 计许的推导过程 E→E+E→E+E*→E+E*→E+i*→计ⅸ E→E+E→计+E→计+E*E→计E→计+i*i E→E*→E*i→E+E*i→→E+i1→计+i*1
举例: 已知G(E) E→E+E│E*E│(E)│i i+i*i的推导过程 E E+E E+E*E E+E*i E+i*i i+i*i E E+E i+E i+E*E i+i*E i+i*i E E*E E*i E+E*i E+i*i i+i*i
2.句型和句子 设文法G=(VnVS,P),若S,α∈V*,则称α为 文法G的一个句型 若上述a∈V,则称是一个句子,即只含终结 符的句型是一个句子
2. 句型和句子 设文法G=(VT,VN,S,P), 若S α, αV*, 则称α为 文法G的一个句型。 若上述α VT，则称α是一个句子，即只含终结 符的句型是一个句子。 * *
3.文法产生的语言 文法G=(VnVN,S,P)的句子的全体,称为由文法 G产生的语言,记为L(G)即 L(G)={a|S→b入a∈V*}
3. 文法产生的语言 文法G=(VT,VN,S,P)的句子的全体, 称为由文法 G产生的语言, 记为L(G), 即 L(G)={α│S +αα VT*}