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é.
La solution
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 ...
Autres conseils
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.
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.