Traduire une grammaire récursive à droite dans forme normale de Chomsky

Question

Je suis en train de faire un exercice où je traduis une grammaire en forme normale de Chomsky. Je comprends comment faire cela dans des circonstances normales, mais cette fois la grammaire je travaille avec est juste récursive. (Techniquement, la grammaire est la réponse à la question précédente, donc je pourrais avoir juste le mauvais gamma.)

Je pense que je peux le faire en utilisant une séquence fixe des règles en place des règles e mais je veux assurer que je ne suis pas aller dans la mauvaise direction. Il est plus facile d'expliquer avec un exemple:

Pour une grammaire qui produit n « a 'où n est supérieur à 0 et un multiple de trois: (ne vous inquiétez pas, cela est tout à fait différente de la grammaire mon exercice effectif)

S-> Aaaa
A-> Aaaa
A-> ε

Est-ce que correcte traduction soit:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

Bien que votre grammaire est juste récursif, vous pouvez effectuer la transformation forme normale de Chomsky comme vous le feriez pour tout autre grammaire (non-droit récursive). Il suffit de suivre l'algorithme décrit dans votre livre, qui se compose probablement de deux étapes: (1) remplacer toutes les occurrences de terminaux a par des règles A -> a , où A ne se produit pas dans l'ensemble de règles; (2) transformer toutes les règles A -.> W , où len (w)> 2, par des règles de longueur 2 contenant des variables fraîches

Pour A règle, alors, construire une règle pour les terminaux dérivés, disons K -> a , et remplacer toutes les occurrences du terminal a :

A -> AKKK

Ensuite, mettre la grammaire dans CNF

A    -> AA'
A'   -> KA''
A''  -> KK