BNF corrispondenza grammatica

Question

Il mio insegnante mi ha dato due grammatiche BNF:

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

e quattro corde da abbinare con loro:

• DFFD
• dddefddfe
• dedf
• deded

Ho capito due di loro, ma gli altri due mi hanno messo in difficoltà. Io non voglio che nessuno mi dica le risposte, ma se qualcuno mi potrebbe dare qualche suggerimento su dove sto andando male sarebbe molto apprezzato.

Answer 1

Hmmm ...

Per induzione, tutte le partite devono avere un numero dispari di caratteri. Quindi, nessuna delle stringhe di 4 caratteri può essere un successo ...

---

Oh aspetta. Ho appena notato la 'Y' nella prima regola. Sappiamo di cosa si tratta? Si potrebbe rompere la mia tesi destra aperta ...

Answer 2

Questa è una grammatica Context-Free, così si dovrebbe essere in cerca di disegnare un albero sintattico. È quindi possibile vedere quale simbolo non terminale porta a cui ceduto stringa. Questi grammatiche sono abbastanza semplici, in modo da disegnare un albero di analisi dovrebbe essere abbastanza facile da fare a mano.

Answer 3

Il mio consiglio sarebbe quello di disegnare un automi o stato schema finita per te stesso prima di scrivere alcun codice. Farlo a mano con una matita e carta.