grammaire BNF appariement

Question

Mon professeur m'a donné deux grammaires bnf:

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

et quatre cordes pour correspondre avec eux:

• dffd
• dddefddfe
• dedf
• deded

J'ai compris deux d'entre eux, mais les deux autres me ont déconcerté. Je ne veux pas qu'on me dise les réponses, mais si quelqu'un pouvait me donner quelques conseils à où je vais mal, ce serait très apprécié.

Answer 1

Hmmm ...

Par induction, tous les matchs doivent avoir un nombre impair de caractères. Donc, ni des 4 chaînes de caractères peut être un succès ...

---

Oh, attends. Je viens de remarquer le « Y » dans la première règle. Est-ce que nous savons ce qui est? Il pourrait briser mon raisonnement droit ouvert ...

Answer 2

Ceci est une grammaire hors-contexte, donc vous devriez chercher à dessiner un arbre d'analyse syntaxique. Vous pouvez alors voir quel symbole non terminal conduit à qui a rapporté la chaîne. Ces grammaires sont assez simples, donc dessiner un arbre d'analyse syntaxique devrait être assez facile à faire à la main.

Answer 3

Mon conseil serait de dessiner un diagramme des automates ou états finis par vous-même avant de vous écrire de code. Faites-le à la main avec un crayon et papier.