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.
Name:
Anonymous2008-11-10 20:42
>>2
This does not generate aaabbba. i.e., it does not generate more than 2 consecutive b's when you want more a's than b's.
Also. Homework problem.
Name:
Anonymous2008-11-11 0:45
>>3
No, it's a take-home exam problem, and I need a hint.