3 votes 3 votes #10 Is the below language context free? L = { w1cw2 : w1,w2 ∈ {a,b}* , w1≠ w2} As per my analysis it is not. Please verify. Theory of Computation theory-of-computation context-free-language + – Ayush Upadhyaya asked Apr 1, 2017 • retagged Jul 4, 2017 by Arjun Ayush Upadhyaya 3.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Yes, It's not context free. rude answered Apr 1, 2017 rude comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments jatin khachane 1 commented Jan 19, 2019 reply Follow Share @Ayush Upadhyaya if it is like |w1| != |w2| or if it is like |w1| = |w2| then it will be dcfl right ?? 0 votes 0 votes KUSHAGRA गुप्ता commented Oct 5, 2019 reply Follow Share @Ayush Upadhyaya As given in peter linz: This language is CFL. Construct an NPDA that counts to some value k (by putting k tokens on the stack) and remembers the kth symbol. It then examines the kth symbol in $w_{2}$. If this does not match the remembered symbol, the string is accepted. If $w \ \epsilon\ L$ , there must be some k for which this happens. This npda chooses the k non-deteministically. 4 votes 4 votes pandit_shubhanshu commented May 31, 2020 reply Follow Share What if w1w2 instead of w1cw2 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Not context free according to me. Purvi Agrawal answered Apr 1, 2017 Purvi Agrawal comment Share Follow See all 2 Comments See all 2 2 Comments reply Ayush Upadhyaya commented Apr 1, 2017 reply Follow Share The base case I found out was that we would exactly be not able to determine when to push symbols onto the stack and when to pop off.What was your's? 0 votes 0 votes Purvi Agrawal commented Apr 1, 2017 reply Follow Share I thought as w1 is not equal to w2,it can be either less than or greater than w2.Lets assume w1>w2,if we push w1,skip c and try to pop w2,then there would be some symbols left in the stack and hence not context free as stack is not getting empty here. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Here push pop is clear but either w1 > w2 or w2 > w1 . So stack may not be empty. So not CFL. Tinku Das answered Apr 1, 2017 Tinku Das comment Share Follow See 1 comment See all 1 1 comment reply Mandeep Singh commented Apr 1, 2017 reply Follow Share if w1 > w2 or vice versa then w1 != w2 so we can easily tell this is not accepted hence CFL. 0 votes 0 votes Please log in or register to add a comment.