Just as the regular languages are those which can be recognised by a finite state automaton the context free languages are those which can be recognised by what’s called a pushdown automaton, essentially a finite state autmaton with access to a stack.
In addition to the tokens of the language we allow the finite state automaton to use finitely many additional tokens on its stack.
Earlier we considered a language for zeroeth order logic, which had the tokens \({ p }\), \({ q }\), \({ r }\), \({ s }\), \({ u }\), \({ ! }\), \({ ∧ }\), \({ ∨ }\), \({ ¬ }\), \({ ⊃ }\), \({ ⊼ }\), \({ ⊻ }\), \({ ≡ }\), \({ ≢ }\), \({ ⊂ }\), \({ ( }\), \({ ) }\), \({ [ }\), \({ ] }\), \({ \{ }\) and \({ \} }\). We can construct a pushdown automaton which recognises this language.
Our automaton starts by pushing a \({ p }\) onto the stack. It then reads characters one at a time, processing them as follows. In each case where I’ve written that the machine pops a character off the stack I mean that it checks whether the stack is empty, fails, and pops the the top character otherwise. “Fail” here and below just means terminates unsuccessfully.
If there is no character to read then it checks whether the stack is empty and terminates successfully if it is and unsuccessfully if it isn’t.
If the character it read is whitespace it does nothing.
If the character it read is a \({ p }\), \({ q }\), \({ r }\), \({ s }\), \({ u }\) it pops a character off the stack. If the character it popped is a \({ p }\) it pushes a \({ ! }\) onto the stack. Otherwise it fails.
If the character it read is a \({ ! }\) then it continues on to read the next character.
If the character it read is \({ ∧ }\), \({ ∨ }\), \({ ⊃ }\), \({ ⊼ }\), \({ ⊻ }\), \({ ≡ }\), \({ ≢ }\), or \({ ⊂ }\) it pops a character off the stack. If the character it popped is a \({ ∧ }\) it continues on to read the next character. If the character it popped is a \({ ! }\) then it pops off another character and if that character is a \({ ∧ }\) it continues on to read the next character. In all other cases it fails.
If the character it read is a \({ ¬ }\) then it pops a character off the stack. If the character it popped is a \({ p }\) then it pops another character off the stack. If that character is a \({ ∧ }\) then it continues on to read the next character. In all other cases it fails.
If the character it read is a \({ ( }\) then it pops a character off the stack. If that character is a \({ p }\) then it pushes a \({ ) }\), then a \({ p }\), then a \({ ∧ }\), and then another \({ p }\) onto the stack and continues on to read the next character. In all other cases it fails.
If the character it read is a \({ [ }\) then it pops a character off the stack. If that character is a \({ p }\) then it pushes a \({ ] }\), then a \({ p }\), then a \({ ∧ }\), and then another \({ p }\) onto the stack and continues on to read the next character. In all other cases it fails.
If the character it read is a \({ \{ }\) then it pops a character off the stack. If that character is a \({ p }\) then it pushes a \({ \} }\), then a \({ p }\), then a \({ ∧ }\), and then another \({ p }\) onto the stack and continues on to read the next character. In all other cases it fails.
If the character it read is a \({ ) }\) then it pops a character off the stack. If the character it popped is a \({ ) }\) then it continues on to read the next character. If the character it popped is a \({ ! }\) then it pops another character. If that character is \({ ) }\) then it continues on to read the next character. In all other cases it fails.
If the character it read is a \({ ] }\) then it pops a character off the stack. If the character it popped is a \({ ] }\) then it and continues on to read the next character. If the character it popped is a \({ ! }\) then it pops another character. If that character is \({ ] }\) then it continues on to read the next character. In all other cases it fails.
If the character it read is a \({ \} }\) then it pops a character off the stack. If the character it popped is a \({ \} }\) then it and continues on to read the next character. If the character it popped is a \({ ! }\) then it pops another character. If that character is \({ \} }\) then it continues on to read the next character. In all other cases it fails.
Before explaining why this works it may be helpful to trace the computational path for a particular input. I’ll choose \({ \{[(p⊃q)∧(q⊃r)]⊃(p⊃r)\} }\) as my input string. As the computation proceeds we need to keep track of what portion of the input has been read and what the contents of the stack is. The accompanying diagram does this. \[ \begin{array}{cccccccccccccccccccccc} & \{ & [ & ( & p & ⊃ & q & ) & ∧ & ( & q & ⊃ & r & ) & ] & ⊃ & ( & p& ⊃& r& ) & \} \\ \hline p & p & p & p & ! & p & ! & ∧ & p & p & ! & p & ! & ] & ∧ & p & p & ! & p & ! & \} \\ & ∧ & ∧ & ∧ & ∧ & ) & ) & p & ] & ∧ & ∧ & ) & ) & ∧ & p & \} & ∧ & ∧ & ) & ) \\ & p & p & p & p & ∧ & ∧ & ] & ∧ & p & p & ] & ] & p & \} & & p & p & \} & \} \\ & \} & ] & ) & ) & p & p & ∧ & p & ) & ) & ∧ & ∧ & \} & & & ) & ) \\ & & ∧ & ∧ & ∧ & ] & ] & p & \} & ] & ] & p & p & & & & \} & \} \\ & & p & p & p & ∧ & ∧ & \} & & ∧ & ∧ & \} & \} \\ & & \} & ] & ] & p & p & & & p & p \\ & & & ∧ & ∧ & \} & \} & & & \} & \} \\ & & & p & p \\ & & & \} & \} \end{array} \]
The interpretation of the diagram is that the column below each input character is the state of the stack after reading it and doing all the associated stack operations. To the left all the input characters there’s a column with just a single \({ p }\), which represents the state of the stack just before reading the first character.
At no point before the end of the input does the automaton terminate unsuccessfully and the stack is empty at the end so the automaton terminates successfully. In other words, this string is recognised as a member of the language.
You may have guessed how this automaton uses its stack. After processing a character the stack shows one valid continuation for the input at that point. This continuation is chosen in such a way that even if the next input character is not the first character of that continuation, i.e. the character at the top of the stack, we can easily adjust the stack to get a valid continuation of the new input string, if there is such a valid continuation, and fail if there is none. This is a strategy which happens to work for this language and some others. It does not work for context free languages in general though.
One feature of the pushdown automaton described above is that it always terminates, either successfully or unsuccessfully. This is clear because at each stage we read an input character and eventually we run out of input. Another feature of the automaton is that it is deterministic. Whenever we read an input token, check whether the stack is empty, or pop a token from the stack there is at most one way to continue the calculation, although there may be none in those cases where we terminate unsuccessfully. These two features are desirable but neither of them is required. Pushdown automata are allowed to have multiple options for their next step. As with all non-deterministic computations we consider we say that the input is accepted if there is some computational path which terminates successfully, even if others terminate unsuccessfully or not at all.