Pushdown Automata, Context Free Grammars, and Context Free Languages

We are moving on.

Recall where we are going:  We are examining the universe of all problems through the lens of models of computation. We are restricting our study to decision problems, problems whose instances all have "yes" or "no" answers (which is the same as "accept" or "reject" when it comes to processing an input string).  We restrict ourselves to decision problems because they are easier to examine from the standpoint of thoery, and they also are good enough for our purposes of trying to categorize problems based on their complexity.

We have discovered that the first model of computation we studied, the finite state automaton (FSA), could solve a number of problems, such as

• whether a binary string has even parity.
• whether a string of ASCII symbols forms a valid variable name in a particular programming language
• whether N mod 5 = 3, for any binary number N

We also discovered that the FSA model is not powerful enough to compute a lot of other important and interesting problems, such as

• L = {0ⁿ1ⁿ | n ≥  0}
• L = {ww^r | w in {0,1}*, and w^r is the reverse of w}
• whether a binary number N is prime or not