Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$$L = \{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\}$$
I think the given language is CSL as i can break this language like this
$$L = \{a^i b^j c^k \mid i \le j \text{ and } j = k\} \cup \{a^i b^j c^k \mid j \le i \text{ and } j = k\} \cup \{a^i b^j c^k \mid i \le j \text{ and } j \le i \text{ and } j = k\}$$
Last language i,j are independent, hence DCFL.
When we take union of these languages, we get CSL.
Is my approach right?
There are two possible interpretations of the condition on $i,j,k$:
$(i \leq j \lor j \leq i) \land j = k$. This condition is equivalent to just $j = k$, and so the language in question is $\{ a^i b^j c^j : i,j \geq 0 \}$, which is a prototypical context-free language.
$i \leq j \lor (j \leq i \land j = k)$. A linear-bounded automaton can decide this language (exercise), so it is context-sensitive. On the other hand, using the pumping lemma you can show that it is not context-free (exercise).
I would guess that the second interpretation is the one that was intended.
It is CFL. Number of a & b are irrelevant. What matters is number of b should be equal to number of c which can be achieved by PDA.
{a^i b^j c^k | i≤j or (k=j≤i)}from the title/rev 1-3.) $\endgroup$ – greybeard Dec 27 '16 at 12:04