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).

a) Give a context free grammar for the language.

b) Construct a PDA from your grammar in based on a).