编译原理 龙书答案(3)

编译原理 龙书答案

b) 试证明该文法产生所有布尔表达式 证明：

一、首先证明文法产生的所有符号串都是布尔表达式

变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式 最短的推导过程得到true、false，显然成立 假定对步数小于n的推导命题都成立

考虑步数等于n 的推导，其开始推导步骤必为以下情况之一 bexpr bexpr or bterm bexpr bterm

bterm bterm and bfactor bexpr bfactor

bfactor not bfactor bfactor ( bexpr )

而后继推导的步数显然<n，因此由归纳假设，第二步句型中的NT推导出的串均为布尔表达式，这些布尔表达式经过or、and、not运算或加括号，得到的仍是布尔表达式 因此命题一得证。

二、证明所有布尔表达式均可由文法生成

变换命题——所有析取式均可由bexpr推导出来，所有合取式均可由bterm（bexpr）推导出来，所有对子布尔表达式施加not运算或加括号或简单true、false都可由bfactor（bexpr、bterm）推导出来

最简单的布尔表达式true和false显然成立

假定对长度小于n的布尔表达式，均可由文法推导出来

考虑长度等于n的布尔表达式B，显然，B只能是以下形式之一 B = B1 or B2 B = B1 and B2 B = not B1 B = ( B1 )

以上几种情况，B1、B2的长度均小于n

对于情况1：B为析取式，B1可为析取式也可为合取式，B2为合取式，根据假设可由bexpr合bterm推导出来，显然可构造推导过程，由bexpr推导出B 其他情况类似，命题二得证

综合一、二，可知文法产生的语言就是布尔表达式 c)