0
$\begingroup$

I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG.

I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue.

I have thought about dividing it into 3 cases then taking the union of them for example:

$i=0, j=3k$

$i=3k, j=0$

But this still hasn't gotten me very far

Any help would be appreciated Thanks

$\endgroup$
1
$\begingroup$

I am not sure whether it is a good idea to actually provide the grammar here in an answer but since the grammar is actually fairly easy I cannot see which details I could hide in a hint, so here it is:

$G = (\{S, A\}, \{a, b, c\}, P, S)$ with $$ P = \{S \to aaaSc \mid aabAc \mid abbAc \mid bbbAc \mid \varepsilon, A \to bbbAc \mid \varepsilon\}.$$ You start by adding three $a$s for each $c$, after finitely many (possibly 0) applications of the first rule, you start creating three $b$s for each $c$ but one time you may actually add 2 $a$s, 1 $b$ for one $c$ or 1 $a$, 2 $b$s for one $c$ (2nd and 3rd rule, respectively).

$\endgroup$
0
$\begingroup$

$L = \{a^i b^j c^k \mid i+j=3k\}$. You need to match up two counts; this can only be done by having a middle-recursive set of rules that generate both parts in correct proportions. All you need is $X \Rightarrow^+ \alpha X \beta$, with $\alpha$ generating 3 $a$s and $b$s, $\beta$ generating 3 $c$s. This can be a single rule, and $X$ can just be the start symbol $S$, so let's start with

$S \rightarrow\epsilon \mid T S ccc$

$T$ must generate $a^ib^{3-i}$ for all $i$, a finite language, so we can just have a rule for each member:

$T \rightarrow aaa \mid aab \mid abb \mid bbb$

We can substitute $T$ into the rule for $S$ to arrive at PHPNick's answer.

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