[Math] Find grammar for given language

context-free-grammar

I want to practice finding grammars for given languages. Unfortunately after solving some easy examples I found out that I completely don't know how to approach these more ambitious. For example when the task is to find grammar for $\left\{ a^i b^{i+2j}c^j: i,j\ge 0 \right\}$ it is very simple and after one minute I have a solution: $$S\rightarrow XY \\ X\rightarrow aXb \ | \ \varepsilon \\ Y\rightarrow bbYc \ | \ \varepsilon$$
However it has been 5 hours since I tried these examples:

a) $\left\{ a^{n^2} : n\ge 1 \right\}$

b) $\left\{ a^{2^n} : n\ge 1 \right\}$

c) $\left\{ a^n b^n c^n : n\ge 1 \right\}$

d) $\left\{ x\in \left\{ a,b,c \right\}^* : count_a(x) = count_b(x) = count_c(x) \right\}$

where $\left\{ a,b,c \right\}^*$ denotes set of all words consisting of letters $a,b,c$, and $count_a(x)$ is the number of occurrences $a$ in word $x$.

And I still can't manage to find grammars for above sets. Can anyone help?

Best Answer

None of the four are context free, no wonder you didn't get grammars for them. By Parikh's theorem, for (a) and (b) the length of the strings must be a semilinear set, that is, representable by a finite number of expressions of the form $\alpha k + \beta$, and that is impossible as the distance from $n^2$ to $(n + 1)^2$, and from $2^n$ to $2^{n + 1}$, grows without limit.

For (c), by the pumping lemma for context free languages, assume for the sake of contradiction that the language is context free, and let $p$ be the constant of the lemma. Then $s = a^p b^p c^p$ is longer than $p$, so it can be written $s = u v x y z$ with $v$, $y$ not both empty such that $u v^k x y^k z$ is part of the language for all $k \ge 0$. But by repeating $v$ and $y$ at most two of $a$, $b$, $c$ can grow while maintaining the general form of $a$s followed by $b$s and then $c$s, and the equality isn't maintained.

For (d), the context free languages are closed with respect to intersection with regular languages (see here). But the intersection of this language with $a^* b^* c^*$ is precisely the non-context free language of (c), so it can't be context free.

Related Question