Pushdown Automaton (PDA) Example: {0^n 1^n}

Here we derive a PDA for the infamous non-regular language {0^n 1^n : n at least 0}. We give some tips as well for how to solve other PDAs. The general aspect here is to "match" 0s with 1s by pushing 0s onto the stack, and popping the 1s in tandem. There is some complication with popping an empty stack, so we push a "dummy" character on the stack to detect when the matching has concluded to avoid this problem. What is a pushdown automaton? It is a finite state machine, where on each transition, items can be pushed or popped off of a stack it has, which has unlimited height. See https://www.youtube.com/watch?v=Br44Zxv84-Q&ab_channel=EasyTheory for more details. ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.