My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize the automaton in action.

What mean in visualizing is, for example, this, a non-deterministic finite automaton that accepts a*+(a.b)*. You can actually try it here. In the lower left corner there is a input field for the word you wanna try and on it’s right side there is a button that starts the process. For each letter being consumed you have to click once inside the canvas, or you can select the “Leitura automática” button for automatic reading. BTW, the source code is here, even though I don’t expect anyone to understand it, it is not well written and the documentation is almost non-existent (and it’s also written in Portuguese).

I read in the internet about a deterministic PA, but this approach with the single stack is not helpful if I wanna build automata that can follow multiple paths at once(like my finite non-pushdown one, that tests all possible paths at once, instead of trying one and backtracking if it fails). So I don't know if I'm in the right place, but my question is: how can I do something similar for a non-deterministic pushdown automata?

  • $\begingroup$ It's not really clear to me what your question is. Are you trying to understand how NPDAs work? Are you asking for suggestions about how to give an animation of an NDPA running on some string? Something else? I don't think that animation suggestions would be on-topic here (or anywhere else that I can think of on Stack Exchange). $\endgroup$ – David Richerby Jun 12 at 9:13
  • $\begingroup$ I know how it works. I'm just wondering about the animation. Sorry if I'm in the wrong place. $\endgroup$ – Wellington Cesar Jun 13 at 1:40
  • $\begingroup$ Yeah, I don't think that's on-topic, here. Honestly, if I had any idea of how to animate that, I'd suggest it, but there are potentially exponentially many different things going on at the same time. The best I can think of is to animate a couple of example paths through the machine but even two at a time probably isn't usefully watchable. $\endgroup$ – David Richerby Jun 13 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.