一、 问答题

问答第1题
　　写一文法，使其语言是偶正整数的集合。 要求：
　　(1) 允许0打头；
　　(2)不允许0打头。


问答第2题
　　证明下述文法G[〈表达式〉]是二义的。
　　〈表达式〉∷=a|(〈表达式〉)|〈表达式〉
　　〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/


问答第3题
　　令文法G[E]为：
　　E→T|E+T|E-T
　　T→F|T*F|T/F
　　F→(E)|i
　　证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。


问答第4题
　　给出生成下述语言的上下文无关文法：
　　（1）{ aⁿbⁿa^mb^m| n，m>=0}
　　（2） { 1ⁿ0^m 1^m0ⁿ| n，m>=0}


问答第5题
　　给出生成下述语言的三型文法：
　　(1) { aⁿb^m|n,m>=1 }
　　(2){aⁿb^mc^k|n,m,k>=0 }


问答第6题
　　给出下述文法所对应的正规式：
　　S→0A|1B
　　A→1S|1
　　B→0S|0