Consider the CFG G defined by productions
S->aSbS|bSaS|e
Prove that L(G) is the set of all strings with an equal number of a's and b's.
The point of inductive proof is that for arbitrary string s with equal a's and b's longer than k,k>=1, we can always find substrings x,y such that s=axby or s=bxay and x,y has equal number of a's and b's respectively.
You can click on the following image to see a zoomed version if it's too small. (Please don't copy it for your homework)
My proof here is clumsy, hope someone would show me an elegant one.
I found another solution by accident today (March 21, 2008) at http://www.cs.iit.edu/~cs532/HW/HW_04_Solution.pdf
The idea is almost the same, and it's also wordy.
No comments:
Post a Comment