Build CFG for $L=\{a^ib^kc^i| \,(i+k)\equiv1 \pmod 3\}$

Question

So I need to find CFG for $$L=\{a^ib^kc^i| \,(i+k)\equiv1 \pmod 3\}$$ and I'm clueless. Can someone please explain how to approach this? Thanks in advance!

Answer 1

The tricky part of the problem is that you have you have to manage states that keep track of what $k\bmod 3$ is so that you can only terminate when you have an appropriate number of $b$'s. Here is a grammar that does that (where your initial state is $S$). $$S\to aTc\mid bV\\T\to aUc\mid V\\U\to aSc\mid b^2V\\V\to b^3V\mid\epsilon$$