1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is the language? For any $i$ and $j$, either $i\leq j$ or $j\leq i$, so that condition does nothing. $\endgroup$ – David Richerby Sep 17 '16 at 10:50
  • $\begingroup$ $i≤j \text{ and } j≤i$ iff $i=j$, but where does this language/condition come from in the first place? $\endgroup$ – greybeard Dec 27 '16 at 12:00
  • $\begingroup$ (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.) $\endgroup$ – greybeard Dec 27 '16 at 12:04
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ you've helped a lot ! Thanks to you for many of your dedicated wonderful answers :) $\endgroup$ – void Jan 29 '18 at 8:42
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.