12 votes 12 votes 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? $L$ is regular but not context-free $L$ is context-free but not regular $L$ is decidable but not context free The complement of $L,$ defined as $\overline{L} = \left \{ a,b,c \right \}^{*}\backslash L,$ is regular. $L$ is regular, context-free and decidable Theory of Computation tifr2018 identify-class-language theory-of-computation + – Arjun asked Dec 10, 2017 • edited Dec 3, 2019 by ankitgupta.1729 Arjun 2.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
18 votes 18 votes $\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. Rameez Raza answered Dec 10, 2017 • edited Jun 15, 2018 by Milicevic3306 Rameez Raza comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments `JEET commented Nov 11, 2019 reply Follow Share Where is LBA here? 0 votes 0 votes Doraemon commented Nov 11, 2019 reply Follow Share linear bounded automata 0 votes 0 votes Satbir commented Nov 11, 2019 i edited by Satbir Nov 11, 2019 reply Follow Share LINEAR BOUNDED AUTOMATA. LINEAR means length of tape is linear in terms of its input. BOUNDED means the tape is bounded from both sides. 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes 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. Manoja Rajalakshmi A answered Dec 10, 2017 • edited Dec 6, 2018 by Manoja Rajalakshmi A Manoja Rajalakshmi A comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Manoja Rajalakshmi A commented Dec 10, 2017 reply Follow Share So you are saying we should not take all the three cases at once in the conditions given under "or"? 0 votes 0 votes Anu007 commented Dec 10, 2017 reply Follow Share yes , all remaining condition comes under by default take any string and see it belongs to language. 1 votes 1 votes Ruchi Vora commented Dec 3, 2019 reply Follow Share 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 . 0 votes 0 votes Please log in or register to add a comment.