Lecture 11 (PDAs), 2/27/06

Concepts, definitions (in italics):

• {w over {a,b}* : w contains equal number of a's and b's} is a context-free language, because there is a CFG for it
• Pushdown Automata (PDAs): NFAs with a stack
• PDA transitions: read char, pop stack, push stack
• Our PDAs are non-deterministic.
• PDA, PDA computation, language of a PDA: formal definitions
• NFAs are a special case of PDAs (every NFA is easily converted to an equivalent PDA)
• PDAs are strictly more powerful than NFAs
• To accept a string, a PDA must be in a final state and have read all the input (just as for FSAs); however, it need not have an empty stack.
• We will be showing that CFGs and PDAs have the same expressiveness. This, together with the fact that NFAs are a special case of PDAs, will give us an alternate proof of the theorem that regular languages are a subset of CFLs.

Reading:

• Chapter 2.2 to end of p. 114

Skills:

• Know new definitions, understand new concepts.
• Given a PDA M and a string w, show an accepting computation of M for w (as a sequence of transitions)
• Understand how to convert an NFA to a PDA

Notes:

• Here is the Wikipedia page about Normal Forms. It lists Chomsky Normal Form, as well as Greibach Normal Form for context-free grammars. It also has many others, from such fields as logic, databases, and linear algebra.

• Question: design a CFG for the language L = {w in {a,b}* : w contains equal number of a's and b's}. 

1. Consider any string w in L.  Imagine going along the string from left to right keeping a tally as follows: Start the tally at 0, add 1 for every a, subtract 1 for every b.  Our tally will be 0 at the end, and it may also be 0 in places along the way.  Here is an example for aabbba, where we show the characters followed by the tally
                0 a 1 a 2 b1 b 0 b -1 a 0

2. Break up w into substrings at points where the tally is 0.  For example, aabbba gets broken up into aabb and ba.  Note that, since the tally is 0 at the beginning and at the end of each substrings, each of them must contain an equal number of a's and b's.  Also, the tally is never 0 in the middle of any substring.

3. Each of these substrings from step 2 ends in a different character than it starts.  This is proved by contradiction: Suppose it starts and ends in the same character. Case 1: it's an a. Then, the tally is 1 after the first a, and it's -1 before the last a.  Therefore, it must have been 0 in the middle, which is a contradiction.  Case 2 (it's a b) is symmetric.

4. Therefore, each string in L can be represented as 0 or more of these strings with an equal number of a's and b's that start and end in a different character. The desired grammar is as follows

   S -> e  |  SX

   X -> 0S1 | 1S0

• We saw PDA for {0ⁿ1ⁿ}
• Deterministic PDAs can also be defined; their expressiveness is between that of DFAs/NFAs and of PDAs