Question

The language {a^i b^j c^k|i<j<k} is
A. regular but not finite
B. context-free but not regular
C. context-sensitive but not context-free
D.recursive or type-0 but not context-sensitive

Answer 1

Answer on Question#38647 – Math - Other

The language $L = \{a^i b^j c^k \mid i < j < k\}$ is not a context-free.

If $L$ were context free, then the pumping lemma should hold.

Let $z = a^{n}b^{n + 1}c^{n + 2}$. Given this string and knowing that $|z| \geq n$, we want to define $z$ as $uvwxy$ such that $|vwx| \leq n$, $|vx| \geq 1$. Because $|vwx| \leq n$, there are five possible descriptions of $uvwxy$:

1. $vwx$ is $a^p$ for some $p \leq n, p \geq 1$

2. $vwx$ is $a^p b^q$ for some $p + q \leq n, p + q \geq 1$

3. $vwx$ is $b^p$ for some $p \leq n, p \geq 1$

4. $vwx$ is $b^{p}c^{q}$ for some $p + q \leq n, p + q \geq 1$

5. $vwx$ is $c^q$ for some $i \leq n, i \geq 1$

Note that because $|vwx| \leq n$, $vwx$ cannot contain both "$a$"s and "$c$". For all of these cases, $uv^iwx^j y$, $i \geq 0$, should be in the language.

In case 1, if $i = 2$ we will be adding an $a$ to the string, making the number of "$a$"s $n + 1$ and thus the string is not in the language. The same argument holds for case 3 in which the number of "$b$"s will be equal to the number of "$c$"s. A similar argument holds in case 5.

In case 5 if $i = 0$ then the number of "$c$"s will be less than or equal to the number of "$b$"s.

In case 2, when $i = 2$ either the number of "$a$"s will be greater than the number of "$b$"s or the number of "$b$"s will be greater than the number of "$c$"s (depending on the distribution of $v$ and $x$).

In case 4, when $i = 0$ either the number of "$b$"s will be less than or equal to number of "$a$"s or the number of "$c$"s will be less than or equal to the number of "$b$"s (depending on the distribution of $v$ and $x$).

Answer: C.