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?

$\endgroup$
3
  • $\begingroup$ What is the language? For any $i$ and $j$, either $i\leq j$ or $j\leq i$, so that condition does nothing. $\endgroup$ Sep 17, 2016 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, 2016 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, 2016 at 12:04

2 Answers 2

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.

$\endgroup$
1
  • $\begingroup$ you've helped a lot ! Thanks to you for many of your dedicated wonderful answers :) $\endgroup$
    – void
    Jan 29, 2018 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.

$\endgroup$
2
  • $\begingroup$ It is OR not AND. For, AND it is definitely DCFL $\endgroup$
    – Garrick
    Sep 17, 2016 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, 2016 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.