COMP 170 Homework 3, due 6 October in class

1. Construct a Chomsky normal form grammar for the language of all strings of the form 0ⁿ1^m where m is either equal to n or equal to 2n.
2. Construct a pushdown automaton for the language in Problem 1.
3. Construct a pushdown automaton for the language of all strings of the form (10)ⁿ(101)ⁿ where n is a nonnegative integer. This language contains the empty string, 10101, and 1010101101, but not 1010101 nor 10101101.
4. Give a context-free grammar (not necessarily in Chomsky normal form) for the language in problem 3.