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.6k 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 Tesla! commented Dec 10, 2017 reply Follow Share please explain logic 0 votes 0 votes krish__ commented Dec 10, 2017 reply Follow Share $\left \{ a^nb^nc^k\right \} \cup \left \{ a^kb^nc^n \right \}\cup \left \{a^nb^kc^n\right\}$ is CFL, since the union of CFLs is again CFL. 9 votes 9 votes minal commented Sep 15, 2018 reply Follow Share what strings getting by option D) ? 0 votes 0 votes tusharp commented Nov 17, 2018 reply Follow Share @minal apbqcr such that !(p=q or q=r or r=p) i.e !p=q and !q=r and !r=p 0 votes 0 votes rfzahid commented Dec 27, 2018 reply Follow Share L also contains strings of the form a^nb^nc^n because the condition is fulfilled by anyone out of p=q or q=r or r=p. This makes L CSL right? 0 votes 0 votes Satbir commented Jul 26, 2019 reply Follow Share No. for CSL the condition should have been p=q AND q=r AND r=p 0 votes 0 votes Sambhrant Maurya commented Aug 11, 2019 reply Follow Share @Satbir @tusharp L cannot be implemented using a DCFL right? 0 votes 0 votes Satbir commented Aug 11, 2019 reply Follow Share right... it can be implemented using NCFL and not DCFL. 1 votes 1 votes Shaik Masthan commented Oct 4, 2019 reply Follow Share why D is wrong ? note :- redefined the term " complement of L" 0 votes 0 votes mitesh kumar commented Oct 30, 2019 reply Follow Share Sir ,in this question there is be case that all condition are true at the same time which leads to CSL. and we have take union of all the case ie (CFL U CSL ) so why not option C ? 0 votes 0 votes Satbir commented Oct 30, 2019 reply Follow Share @mitesh kumar All conditions can be true at same time For accepting the string belonging to the language , only one condition true at a time is sufficient (even if all conditions are true.) Hence it is a CFL. we have take union of all the case ie (CFL U CSL ) We don't do like this. First we check for CFL, if we cannot prove that it is CFL then we go for CSL check. All CFL are CSL. eg:- (a+b)* is Regular language , CFL, CSL. Thats why option C is wrong. 1 votes 1 votes Doraemon commented Nov 11, 2019 reply Follow Share Here L is NCFL . Its complement L' is not CFL, it is CSL as the complement of the language L is defined as: L'={all strings of the form a^p b^q c^r such that p!=q!=r} It cannot be done using 1 stack. Every NCFL is decidable. And also L is not regular. So option B 0 votes 0 votes Doraemon commented Nov 11, 2019 reply Follow Share @Satbir In case of the LBA the length of the tape is equal to the length of its input. or is a constant multiple of the length of the input? 0 votes 0 votes `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.