32语言和文法 323验证文法产生的语言 G:S→(S)S|EL(O)=配对的括号串的集合 按串长进行归纳:配对括号串可由S推出 归纳基础:S→E 归纳假设:长度小于2n的都可以从S推导出来 归纳步骤:考虑长度为2n(n≥1)的w=(x)y S→(S)S→*(x)S→*(x)3.2 语言和文法 3.2.3 验证文法产生的语言 G : S → (S) S |  L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出 –归纳基础： S   – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n  1)的w = (x) y S  (S)S * (x) S * (x) y