0 votes 0 votes Consider the language defined as L = { $a^pb^qa^r$ | p = q or q = r} . L complement is Regular CFL but not regular CSL but not CSL DCFL Theory of Computation theory-of-computation grammar + – Abhipsa asked Jan 22, 2019 • reshown Jan 22, 2019 by Abhipsa Abhipsa 382 views answer comment Share Follow See 1 comment See all 1 1 comment reply prashant jha 1 commented Jan 22, 2019 reply Follow Share Complement shall be p!=q and q!=r CSL it must be 1 votes 1 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes Actually the language L is CFL, and we know that CFL are not closed under Compliment and Intersection. So compliment of given language will be CSL. Sumit Rana 1 answered Jan 22, 2019 • selected Jan 22, 2019 by Abhipsa Sumit Rana 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply balchandar reddy san commented Jan 22, 2019 reply Follow Share L is Non-deterministic context free right? 0 votes 0 votes Sumit Rana 1 commented Jan 22, 2019 reply Follow Share @balchandar reddy san Yes L is Non-Deterministic Context Free Language. We generally use NDCFL as CFL only and Deterministic Context Free Language as DCFL. 0 votes 0 votes Please log in or register to add a comment.