My teacher has given me two bnf grammars:
A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'
and four strings to match with them:
I've figured out two of them, but the other two have me stumped. I don't want anyone to tell me the answers, but if someone could give me some hints as to where I'm going wrong it would be much appreciated.
My advice would be to draw a finite automata or state diagram for yourself before you write any code. Do it out by hand with a pencil and paper first.
Hmmm...
By induction, all matches must have an odd number of characters. So neither of the 4 character strings can be a hit...
Oh wait. I just noticed the 'Y' in the first rule. Do we know what that is? It could break my argument right open...
This is a Context-Free grammar, so you should be looking to draw a parse tree. You can then see which non-terminal symbol leads to which yielded string. These grammars are fairly simple, so drawing a parse tree should be fairly easy to do by hand.