Question

The language {a^i b^j c^k| k= max(i,j)} os
A. regular but not context-free
B. context-free but not regular
C. context-sensitive but not context-free
D.recursive but not context-sensitive

Answer 1

Answer on Question#38645 – Math - Other

Suppose that $p$ is a pumping length for $L$, and consider the string $s = a^{p}b^{p}c^{p}$. Using pumping lemma for context-free languages we may rewrite $s$ as $uvxyz$ where

1. $|vxy| \leq p$;

2. $|vy| \geq 1$;

3. $uv^{n}xy^{n}z \in L$ for all $n \geq 0$.

We can see that the language not context-free but regular.

Answer: A.