1) Draw the state diagram for a PDA that recognizes bitstrings of the form an bm where 0 ? m < n. That means some number of as (at least 1) followed by a smaller number of bs (possible zero). Some strings in the language: a, aa, aab, aaa, aaab, aaabb, aaaa, aaaab, aaaabb, aaaabbb etc. Your PDA must have stack alphabet ? = {$, X} and input alphabet {a, b}. The PDA should push Xs onto the stack to record how many as were read from the input string. After that it should pop the stack for each b read in (or until the stack is empty).

2) Give a context free grammar for the language in question 1.

3) Using the construction we discussed in class (an in Sipser), construct a PDA from your grammar in Question 2. This will be a completely different PDA from Question 1 since youre constructing it from a CFG this time.