对于2.2.5的答案可能有更好的解法

[ze-mu-zhou]

第一个语言很明显是由 11、1001 和 0 这三种终结符号组成的。而且，0 不会出现在最左边

当 n=1 时，文法生成的串为 11 或 1001，其值分别为 3 和 9，都能被 3 整除

归纳假设：假设对于长度为 k 的由该文法生成的所有二进制串 s∈S，其值 v(s) 能被 3 整除

归纳步骤：

对于长度为 k+1 的二进制串：

如果是由 num0 生成（其中 num 是长度为 k 的串），设 num 对应的值为 v(u)，那么 num0 对应的值为 2v(u)
因为 v(u) 能被 3 整除，所以 2v(u) 也能被 3 整除

如果是由 num1num2 生成，其中 num1 和 num2 都是长度小于 k+1 的串且 v(num1) 和 v(num2) 能被 3 整除，那么 num1num2 对应的值为 v(num1)+v(num2)
由于 v(num1) 和 v(num2) 都能被 3 整除，所以 v(num1)+v(num2) 也能被 3 整除