3
$\begingroup$

$$\{ a^{k}b^{j} : k = 2j , k \geq 0\}$$

I'm trying to wrap my head around CFG's but I am having trouble. From this language, there should be twice as many a's than b's. Here is my attempt.

$$S \to aSb \ | \ a Sa \ | \ \epsilon $$

$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSabb \Rightarrow aaaabb $$

But, I can also have this arise, which I don't want: $$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb $$

How can I force the CFG to put twice as many a's as b's? Is there any general approach to solving these?

$\endgroup$
2
$\begingroup$

One general approach would be to try writing some initial strings and try to figure out a pattern. In my minimal experience, a lot of the times the strings I miss are of smaller lengths.

The initial strings for this would be:

$(\epsilon, aab, aaaabb, aaaaaabbb, ...)$ and so on.

Here we notice that: a) The string always has to start with an $a$ and b) Every time we generate an $b$, there should be two $a$'s corresponding to it.

So, we can write it as:

$$S \rightarrow \epsilon \ | \ aaSb$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.