BNF grammar matching

Question

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:

• dffd
• dddefddfe
• dedf
• deded

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.

Answer 1

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...

Answer 2

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.

Answer 3

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.