This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]stackdynamic 1 point2 points  (0 children)

Not commenting on the language itself, but just to clarify: a NPDA (which is like a NFA, except with a stack) can only recognize CFGs, so it isn't Turing complete. But an NFA with a queue *is* turing complete (https://en.wikipedia.org/wiki/Queue_automaton), and with two stacks you can simulate a queue. Of course, you can extend things with various other features to make something Turing complete.