Correct Unrestricted Grammar for:

Question

I can't seem to figure out the Unrestricted Grammar for

L = (w am bn | w={a,b}* m=number of a's in w n=number of b's in w).

I've constructed the following grammar for it, but it keeps rejecting every string I enter in JFLAP. But manually creating a parse tree for it gives me no problem. Can anyone look at it for me and see what's wrong?

S -> AST | BSU | epsilon
UT -> TU
T -> A
U -> B
A -> a
B -> b

Answer 1

I've downloaded and used JFLAP on your grammar. I think the issue is that you have not used the notation that JFLAP does for grammar entry. It does not used the | symbol, but you have to supply several rules instead. Therefore in JFLAP notation (and still and valid grammar) you would have:

S -> AST 
S -> BSU 
S -> ε
UT -> TU
T -> A
U -> B
A -> a
B -> b

You would also need to set the empty string as ε in the FLAP preferences. If you can manually create a parse tree you can also do this in JFLAP to show the derivations.