Timeline for Find a pushdown automaton for { x#y ∣ x ≠ y }
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 14 at 15:18 | comment | added | Daniel | I tried to draw the automaton according to your description but I couldn't figure where the symbol $a$ should be, and I also don't quite understand how to translate "memorizes the symbol $x_i$ in its finite control" into drawing. I saw in other posts a CFG to this language and I'm aware that exists algorithm that convert CFG to PDA. Your method is different because you use nondeterminism directly, skipping the CFG. I'm working with Michael Sipser book on the topic and I couldn't found a PDA that use nondeterminism like you wrote. Will it be possible for you do draw the PDA ? | |
| May 8, 2015 at 10:40 | history | answered | babou | CC BY-SA 3.0 |