Timeline for Determine whether two languages are context free
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Sep 26, 2013 at 0:40 | vote | accept | user678392 | ||
| Sep 26, 2013 at 0:19 | comment | added | Subhayan | sorry, it wasn't of much help to you, unless you have already solved it yourself, please ref. to Rapheal's post there for the second question, and mine or Gilles answer here for your first question :) | |
| Sep 23, 2013 at 15:56 | comment | added | user678392 | You are not even answering the same question as the one I'm asking. So how would it help? | |
| Sep 23, 2013 at 7:26 | history | edited | Subhayan | CC BY-SA 3.0 |
added 236 characters in body
|
| Sep 23, 2013 at 7:23 | comment | added | Subhayan | @user678392 please see this. I am pretty confident this is correct. Do you want me to cross post the answer here too? | |
| Sep 23, 2013 at 0:28 | history | edited | Subhayan | CC BY-SA 3.0 |
edited image (added a final state)
|
| Sep 23, 2013 at 0:02 | comment | added | user678392 | Could you please explain why these steps work? we 'copy' the input tape onto the stack (q1) and leverage non-determinism for the check we keep reading off the stack and uninterestingly read while we keep encountering the same variables (q2) if the tape becomes empty, we just don't accept the language (q3) if we see even one position, where there's a difference, we are happy, and read the rest of the string (q4) and check if |x|=|y| | |
| Sep 22, 2013 at 23:48 | comment | added | Subhayan | i have posted the final answer at the link Gilles provided. and i think he's right, you should try to read his desc. and construct your own, and i am sure you can do that :) | |
| Sep 22, 2013 at 23:45 | history | edited | Subhayan | CC BY-SA 3.0 |
added 172 characters in body
|
| Sep 22, 2013 at 23:23 | comment | added | user678392 | oh. very clear. you didn't even need to do the actual pda diagram. so bonus points for that. | |
| Sep 22, 2013 at 23:12 | comment | added | Subhayan | $q0$ is also a final state, apologies, i missed it out while drawing it... | |
| Sep 22, 2013 at 23:09 | history | answered | Subhayan | CC BY-SA 3.0 |