patternMinor
Compute context free grammars for twice the amount
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?
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$$
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.