TIFR CSE 2018 | Part B | Question: 11

Question

Consider the language $L\subseteq \left \{ a,b,c \right \}^{*}$ defined as

$L = \left \{ a^{p}b^{q}c^{r} : p=q\quad or\quad q=r \quad or\quad r=p \right \}.$

Which of the following answer is TRUE about the complexity of this language?

• A. $L$ is regular but not context-free
• B. $L$ is context-free but not regular
• C. $L$ is decidable but not context free
• D. The complement of $L,$ defined as $\overline{L} = \left \{ a,b,c \right \}^{*}\backslash L,$ is regular.
• E. $L$ is regular, context-free and decidable

Answer 1

$\large L1=a^pb^qc^r: p=q$

$\large L2=a^pb^qc^r: q=r$

$\large L3=a^pb^qc^r: r=p$

$\large L=L1\cup L2\cup L3$

$\large  L1,L2,L3$  are CFL

We know that union of  CFL is CFL
Hence, $\large L$ is Context free language

Answer is option B.

Comments

Where is LBA here?

---

linear bounded automata

---

LINEAR BOUNDED AUTOMATA.

LINEAR means length of tape is linear in terms of its input.

BOUNDED means the tape is  bounded from both sides.

Answer 2

The given language L is context free since there is 'or' in between the conditions $p=q, q=r, r=p$. (Union of context free languages is context-free) 

If there were 'and' in between the conditions, the language would be context sensitive.

L is decidable since it is context-free. (All recursive languages are decidable, context free language is a subset of recursive languages)

Complement of L is context-sensitive but not regular.

option B.

Comments

So you are saying we should not take all the three cases at once in the conditions given under "or"?

---

yes , all remaining condition comes under by default take any string and see it belongs to language.

---

How to claim that the language is context sensitive ? Like how can we say if it is accepted by Linear bounded automata or haulting turing machine .