Context Free Grammar Issue

2
votes

For starters this is a homework question. I have an idea but I am still not able to get the correct answer. I'm not asking for the answer I am just asking for help to answer the question.

I am currently trying to write a context free grammar for the language 

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

So basically there are twice as many a's as b's and a d in between the 2. For example: 

d,  adbb,  aadbbbb,  ……

Here is about what I have, I don't have much... I understand the concept of these CFG's I am just not sure about the logic for this question. I am not sure If i am even going the right direction... 

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

Thanks.

2
context-free-grammarlanguage-theory
You mentioned you had an idea. What was it? If you give us an idea of your thought process we might be able to guide it more successfully. – Benn
You mean i and j >= 0 right? It'd be weird for them to be negative. – Pointy
I have added my own work. To give an idea of my thought process – Johnrad

2 Answers

1
votes

Whenever you have a language you can list out like this, where each string in a substring of the following string, its fairly trivial to write a simple recursive grammar. You need a rule to make the first (shortest) string, and a rule to make each longer string from the previous string.

1
votes

I guess I'll start off hints by saying that you only need 2 statements to solve this. I'd rather see some of your work (even in the wrong direction!) if I'm to give you any more, though.

EDIT

Thanks for posting what you've got. Here's a couple thought exercises that will hopefully get you moving in the right direction:

Write a grammar that expresses anbn for n > 0 (ab, aabb, aaabbb, ...)

Wikipedia's article on CFG's has some help on this if you're still stuck.

Write a grammar that expresses andbn for n > 0 (adb, aadbb, aaadbbb, ...)

When you get that last one, you'll see the trivial addition to get to your grammar.