BNF coincidente gramática

Question

Mi maestro me ha dado dos gramáticas BNF

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

y cuatro cuerdas para que coincida con ellos:

• dffd
• dddefddfe
• dedf
• DEDED

He descubierto dos de ellos, pero los otros dos me he dejado perplejos. No quiero que nadie me diga las respuestas, pero si alguien me podría dar algunas pistas en cuanto a donde voy equivocado que sería muy apreciada.

Answer 1

Hmmm ...

Por inducción, todos los partidos deben tener un número impar de caracteres. Así que ninguno de los 4 cadenas de caracteres puede ser un éxito ...

---

Oh, espera. Me he dado cuenta de la 'Y' en la primera regla. ¿Sabemos lo que es? Podría romper mi argumento derecha abierta ...

Answer 2

Esta es una gramática libre de contexto, por lo que debe buscar para dibujar un árbol de análisis sintáctico. A continuación, puede ver qué símbolo no terminal conduce a lo que produjo cadena. Estas gramáticas son bastante simples, por lo que dibujar un árbol de análisis deben ser bastante fácil de hacer a mano.

Answer 3

Mi consejo sería dibujar un diagrama de autómatas de estados finitos o por sí mismo antes de escribir ningún código. Hacerlo a mano con un lápiz y papel.