HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Compute context free grammars for twice the amount

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
twicethefreecomputeamountgrammarsforcontext

Problem

$$\{ 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?

Solution

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$$

Context

StackExchange Computer Science Q#95891, answer score: 2

Revisions (0)

No revisions yet.