比奥数更硬核的题目：equivalence of context free grammar

prove equivalence of context free grammar

比如产生‘a’比‘b’多的字符串，答案给出以下grammar：

S -> TaT
T -> TT | aTb | bTa | a | epsilon

有个学生给出：

S -> B | BA | AB | AS | SA
B -> a | aB
A -> AA | aAb | bAa | epsilon

证明这两个context free grammar （CFG）， 产生相同的language。或证否。

算了，估计大多数做不出来，还是把答案给出来吧：
http://web.cs.unlv.edu/larmore/Courses/CSC456/F10/Assignments/grmundec.html

【 在 edison2012 (jimmy) 的大作中提到: 】
: prove equivalence of context free grammar
: 比如产生‘a’比‘b’多的字符串，答案给出以下grammar：
: S -> TaT
: T -> TT | aTb | bTa | a | epsilon
: 有个学生给出：
: S -> B | BA | AB | AS | SA
: B -> a | aB
: A -> AA | aAb | bAa | epsilon
: 证明这两个context free grammar （CFG）， 产生相同的language。或证否。