PDA for this CFL $L=\{a^i b^j c^k, k=i*j, i,j=0,1,2...\}$

Question

I have troubles constructing pushdown automata for the following language: $L=\{a^i b^j c^k \mid k=i*j; \quad i,j=0,1,2...\}$ .I am not interested in the automata itself, just the idea of handling the product.

Answer 1

It is very reasonable that you are having problems constructing an PDA, because the language is not context-free. We can use the pumping lemma to show this. Let $p$ be the pumping constant from this lemma and consider the word $a^pb^pc^{p\cdot p}\in L$.

Any pumping must affect both $a^pb^p$ and $c^{p\cdot p}$, because otherwise we obtain words not in the language. Since $|vwx|\leq p$ this means that $v\in b^+$ and $x\in c^+$.

Even for the minimal case of $v = b$, $x$ would need to be $c^p$ to arrive at $a^pb^{p+1}c^{p\cdot (p+1)}$. But again because of $|vwx|\leq p$ the factor $x$ could at most be $c^{p-1}$.

So there is no pumping factorization for the word $a^pb^pc^{p\cdot p}$ and consequently $L$ is not context-free.