BNF correspondente gramática

Question

Meu professor me deu dois bnf gramáticas:

A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'

e quatro cordas para combinar com eles:

• dffd
• dddefddfe
• dedf
• DEDED

Eu descobri dois deles, mas os outros dois têm me perplexo. Eu não quero que ninguém me diga as respostas, mas se alguém poderia me dar algumas dicas a respeito de onde eu estou indo errado, seria muito apreciado.

Answer 1

Hmmm ...

Por indução, todos os jogos devem ter um número ímpar de caracteres. Assim, nenhuma das 4 cadeias de caracteres pode ser um sucesso ...

---

Oh esperar. Eu notei o 'Y' na primeira regra. Não sabemos o que é isso? Ele poderia quebrar o meu argumento direito aberto ...

Answer 2

Esta é uma gramática Context-Free, então você deve estar olhando para desenhar uma árvore de análise. Você pode então ver o que leva símbolo não-terminal para que rendeu string. Estas gramáticas são bastante simples, então desenhar uma árvore de análise deve ser bastante fácil de fazer à mão.

Answer 3

Meu conselho seria para desenhar uma autômatos ou estadual diagrama finito para si mesmo antes de escrever qualquer código. Fazê-lo com a mão com um lápis e papel primeiro.