0 votes 0 votes L = (a^n b^n a^n | n = 1,2,3) is an example of a language that is A. context free B. not context free C. not context free but whose complement is CF D. both (b) and (c) Theory of Computation theory-of-computation grammar + – Bhavana Giri asked Mar 31, 2017 • retagged Jun 4, 2017 by Arjun Bhavana Giri 4.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes If n is only 1,2,3 Then it is regular language as it is finite language therefore it is context free If n= 1,2,3.... Then Not context free Because We require two stack Whenever occurence a comes push in one stack Then occurence b comes push in 2nd stack And pop one a and one b from the stack for occurrence of a Rameez Raza answered Mar 31, 2017 Rameez Raza comment Share Follow See 1 comment See all 1 1 comment reply Bhavana Giri commented Mar 31, 2017 i edited by Bhavana Giri Apr 1, 2017 reply Follow Share answer was given as option c) can you also explain how the complement is Context free? 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes n= 1,2,3 Thats it? or 1,2,3.......? IF n=1,2,3 then Regular hence Context Free.. Option A If n=1,2,3...... then not context free. Option B Ahwan answered Mar 31, 2017 Ahwan comment Share Follow See all 4 Comments See all 4 4 Comments reply Bhavana Giri commented Mar 31, 2017 reply Follow Share option c was mentioned as the answer.I understood now that the complement would be n =1,2,3 hence complement is context free. Thanks 0 votes 0 votes Ahwan commented Mar 31, 2017 reply Follow Share C was the given ans ? 0 votes 0 votes Bhavana Giri commented Mar 31, 2017 reply Follow Share yea edit your answer to avoid confusion 0 votes 0 votes Ahwan commented Apr 1, 2017 reply Follow Share But still I am confused.. how the complement of it can be CFL when it is not CFL ! Tell me the logic ... how its complement can be CFL ? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Since n is finite , the language will have finite cases and can be represented by DFA, making it a regular language. All the regular languages are context free languages. Complement of a regular language is regular. Therefore its complement is also context free. If the question is correctly put , Answer is (a). Karan Saini answered Jul 9, 2017 Karan Saini comment Share Follow See all 0 reply Please log in or register to add a comment.