Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Contect-free grammar

Name: Anonymous 2008-11-10 2:52

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: Anonymous 2008-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: Anonymous 2008-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: Anonymous 2008-11-11 0:45

>>3
No, it's a take-home exam problem, and I need a hint.

Name: Anonymous 2008-11-11 5:20

>>2

Damn those consecutive bs!
 
S -> AaA or BbB
A -> AaA or AaAbA or AbAaA or E
B -> BbB or BaBbB or BbBaB or E

S -> AaA -> AaA AaAbAaA -> AaAaAbAbAaA
  -> AaAaAaAbAbAbAaA -> aaabbba

Name: Anonymous 2008-11-13 14:07

Fucking hate contacts, should go back to glasses

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List