Problema de gramática livre de contexto

Question

Para iniciantes, esta é uma questão de lição de casa. Tenho uma ideia, mas ainda não consigo obter a resposta correta. Não estou pedindo a resposta que estou apenas pedindo ajuda para responder à pergunta.

Atualmente, estou tentando escrever uma gramática gratuita de contexto para o idioma

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

Então, basicamente, existem duas vezes mais A que B e o AD entre os 2. Por exemplo:

d,  adbb,  aadbbbb,  …… 

Aqui está sobre o que tenho, não tenho muito ... Eu entendo o conceito desses CFGs que não tenho certeza sobre a lógica para esta pergunta. Não tenho certeza se estou indo na direção certa ...

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

Obrigado.

Answer 1

Acho que vou começar dicas dizendo que você só precisa de duas declarações para resolver isso. Prefiro ver um pouco do seu trabalho (mesmo na direção errada!) Se eu lhe dar mais.

EDITAR

Obrigado por postar o que você tem. Aqui estão alguns exercícios de pensamento que esperamos que você se mova na direção certa:

Escreva uma gramática que expressa umⁿbⁿ para n> 0 (AB, AABB, AAABBB, ...)

O artigo da Wikipedia sobre CFG tem ajuda nisso se você ainda estiver preso.

Escreva uma gramática que expressa umⁿdBⁿ para n> 0 (adb, aadbb, aaadbbb, ...)

Quando você conseguir o último, verá a adição trivial para chegar à sua gramática.

Answer 2

Sempre que você tem um idioma, você pode listar assim, onde cada string em uma substring da string a seguir, é bastante trivial escrever uma gramática recursiva simples. Você precisa de uma regra para criar a primeira string (mais curta) e uma regra para criar cada sequência mais longa da string anterior.