Contexte Grammaire libre Numéro

Question

Pour les débutants c'est une question de devoirs. J'ai une idée mais je ne suis toujours pas capable d'obtenir la bonne réponse. Je ne demande pas la réponse, je demande simplement de l'aide pour répondre à la question.

J'essaie actuellement d'écrire un contexte grammaire libre pour la langue

a(iterated i times)db(iterated j times), for i and j>=0, and j = 2 * i. 

Donc, fondamentalement, il y a deux fois plus d'un est comme B et ad entre les 2. Par exemple:

d, adbb, aadbbbb, …… 

Voici ce que j'ai, je n'ai pas beaucoup ... Je comprends le concept de ces CFG Je ne suis pas sûr de la logique de cette question. Je ne suis pas sûr Si je vais même dans la bonne direction ...

S -> AdB 
A -> EMPTY 
A -> aAB 
B -> DD 

Merci.

Answer 1

Je suppose que je vais commencer en disant que vous n'avez besoin que de 2 instructions pour résoudre ce problème. Je préférerais voir votre travail (même dans la mauvaise direction!) Si je dois vous en donner plus.

EDIT

Merci d'envoyer ce que vous avez. Voici quelques exercices de pensée couple qui nous l'espérons vous faire bouger dans la bonne direction:

Ecrire une grammaire qui exprime une ⁿ b ⁿ pour n> 0 (ab, AABB, aaabbb, ...)

L'article de Wikipedia sur CFG a de l'aide à ce sujet si vous êtes toujours bloqué.

Ecrire une grammaire qui exprime une ⁿ db ⁿ pour n> 0 (adb, aadbb, aaadbbb, ...)

Lorsque vous obtenez ce dernier, vous aurez voir l'addition triviale pour arriver à votre grammaire.

Answer 2

Chaque fois que vous avez un langage que vous pouvez lister comme ceci, où chaque chaîne dans une sous-chaîne de la chaîne suivante, il est assez trivial d'écrire une simple grammaire récursive. Vous avez besoin d'une règle pour créer la première chaîne (la plus courte) et d'une règle pour créer chaque chaîne plus longue à partir de la chaîne précédente.