Pushdown Automaton (PDA) for Non-Regular Language {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.

Easy Theory Website: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio
Patreon: https://www.patreon.com/EasyTheoryYT
Fourthwall: https://easy-theory-llc-shop.fourthwall.com
Problem Solving channel: ​⁠ @easytheoryprobsolve