Difficulty finding context free grammar for this language

93 Views Asked by At

I'm learning context free grammars from languages.

Language ${L=\{{a}^{2i}\,{b}^j\,{c}^k\,|\,3i=j+k, i \gt 0\}}$

My guess is

$${S\rightarrow BA}$$ $${A\rightarrow Aaa|aa}$$ $${B\rightarrow bbbB\,|\,Bccc\,|\,bbAc\,|\,bAcc}$$

Since the word must start with an even number of a.

Am I right?

1

There are 1 best solutions below

0
On

That doesn't seem to be correct since now you can produce an $a$ after $b$, which isn't allowed.

My attempt:

$S \to C_1c | B_1b $

$C_1 \to C_2c | B_1$

$C_2 \to aaC_3c | B_2$

$C_3 \to C_1c | B_3$

$B_3 \to B_1b | \epsilon$

$B_1 \to B_2b$

$B_2 \to aaB_3b$

The idea is that first you make $c$'s and then change the symbol to make $b$'s. You make two $a$'s at the left side every third time. For this you keep track with the lower index in B and C.

EDIT: I forgot the case that you can have zero $c$'s in which case you start to make immediately $b$'s. I also forgot that you need $i>0$ but now it's OK since you cannot make the string empty in the beginning.