Problem Set 4—Context Free Grammars and Pushdown Automata

Purpose

This problem set develops your understanding of the two basic ways of describing a context free language, namely (1) via a context free grammar, and (2) via a pushdown automaton.

Background

This problem set is based on material in sections 2.1 and 2.2 of our textbook. We discussed context free grammars in class on February 19, and pushdown automata on February 22.

Activity

Solve each of the following problems.

Problem 1

Exercise 2.4e in our textbook (give a context free grammar for the set of palindromes over {0,1}). Remember that palindromes can be either even or odd in length.

Problem 2

Exercise 2.5e (give a pushdown automaton that recognizes the language from problem 1 above). I will want to see the state diagram for your automaton when you grade this problem set; you should be able to explain to me how it works, but do not need to write down the “informal description” the book asks for.

Problem 3

Exercise 2.9 in our textbook (give a context free grammar for { aⁱb^jc^k | i = j or j = k }; determine whether your grammar is ambiguous).

Problem 4

Exercise 2.6b in our textbook (give a context free grammar that generates the complement of { aⁿbⁿ | n≥0 }).

Problem 5

Exercise 2.7b in our textbook (give a PDA that recognizes the language in problem 4 above). I will want to see the state diagram for your automaton when you grade this problem set; you should be able to explain to me how it works, but do not need to write down the “informal description” the book asks for.

Problem 6

Show that pushdown automata can “add” in the sense that finite automata cannot, i.e., that there exists a pushdown automaton that recognizes the language { aⁱb^jc^i+j | i,j ≥ 0}.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.