I need a CFG for the language that contains all strings w in {a,b}* such that the number of a's in w does not equal the number of b's in w. Google does nothing.
Name:
Anonymous2008-11-10 8:52
This may not be the most efficient solution, but how about:
S = start state, E = empty string, terminals = {a,b}
S -> aA or bB
A -> AaA or AabA or AbaA or E
B -> BbB or BabB or BbaB or E
ie take path A if you want more a than b, or route B if you want more b than a. You can probably get rid of some of the As and Bs, there are bound to be some redundant ones in there.