# Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?

$$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?

• What is the language? For any $i$ and $j$, either $i\leq j$ or $j\leq i$, so that condition does nothing. – David Richerby Sep 17 '16 at 10:50
• $i≤j \text{ and } j≤i$ iff $i=j$, but where does this language/condition come from in the first place? – greybeard Dec 27 '16 at 12:00
• (I don't think the first formula $$L = \{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\}$$ from rev. 4 correctly reflects the language {a^i b^j c^k | i≤j or (k=j≤i)} from the title/rev 1-3.) – greybeard Dec 27 '16 at 12:04

There are two possible interpretations of the condition on $i,j,k$:

1. $(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.

2. $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.

• you've helped a lot ! Thanks to you for many of your dedicated wonderful answers :) – void Jan 29 '18 at 8:42

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.

• It is OR not AND. For, AND it is definitely DCFL – Garrick Sep 17 '16 at 3:42
• I'm afraid what you're up to but I think you are including subset of the case as another case. – Mr. Sigma. Sep 17 '16 at 3:44