6 votes 6 votes Show that the language L={xy∣|x|=|y|,x≠y} is context free. Do not give links plz explain in simple manner Kaluti asked Nov 28, 2017 Kaluti 3.6k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Red_devil commented Nov 28, 2017 reply Follow Share well we know that L={ww| w∈ (a+b)*} is not CFL then how can it be CFL because we have to eliminate those strings which are of type WW. 0 votes 0 votes Ashwin Kulkarni commented Nov 28, 2017 reply Follow Share I had same Question last night! Still I was waiting for any answer. 0 votes 0 votes joshi_nitish commented Nov 28, 2017 reply Follow Share it is CFL, with non-deterministic PDA, you can check that if there exist some location where bit in x and corresponding bit in y differ, and with embedded DFA you can check whether it is 0mod2. PS: had it been L={xy| |x|=|y|, x=y} , then it would be CSL, because you have to match every bits of x and corresponding bits of y parallely. 2 votes 2 votes just_bhavana commented Nov 29, 2017 reply Follow Share It is not regular right because it is not accepting strings of the form {xy | |x| = |y|, x = y} Had it been just L = {xy | |x| = |y|} we would have a DFA for it as it accepts all even length strings. 0 votes 0 votes chinmaybadjatya commented Sep 12, 2020 reply Follow Share that’s not sound logic because CFL is not closed under complementation. 0 votes 0 votes Mohnish commented Dec 1, 2020 reply Follow Share can you expalin properly @joshi_nitish 0 votes 0 votes avian85 commented Jan 11, 2021 reply Follow Share could you please elaborate how NPDA can be used for this? 0 votes 0 votes chinmaybadjatya commented Jan 15, 2021 reply Follow Share first we have to find the middle point of the string, if the string is odd, we can’t do this. then for ANY character in y, if the top of stack isn’t matching the character, the strings are not equal. 0 votes 0 votes Shiva Sagar Rao commented Feb 2, 2021 i edited by Shiva Sagar Rao Feb 6, 2021 reply Follow Share This question was asked in GATE 2020: https://gateoverflow.in/333199/gate-2020-cse-question-32 Useful CS Stack exchange link to understand why given language is context free: https://cs.stackexchange.com/questions/307/show-that-xy-∣-x-y-x-≠-y-is-context-free 0 votes 0 votes jiminpark commented Dec 1, 2021 reply Follow Share @Ashwin Kulkarni, How can we find that this grammar is CFL? I didn’t understand using the link provided! 0 votes 0 votes dutta18 commented Sep 22, 2022 reply Follow Share Is the language also regular? 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes we can take it as wwr . where x=w and y=wr so |x|=|y| and it is cfl. pragyak26 answered Jan 15, 2021 pragyak26 comment Share Follow See all 2 Comments See all 2 2 Comments reply Siddle commented Nov 30, 2021 reply Follow Share It is also given x=!y x = 101 (w) y = 101 (w^r) for this case above explanation is not valid. 4 votes 4 votes ajayraho commented Dec 13, 2023 reply Follow Share Awesome! Partially correct but most intuitive answer. 0 votes 0 votes Please log in or register to add a comment.