Lehman College, City University of New York

Fall 2016

Grading Notes:

- Submit one answer per group.
- Make sure that the answer is legible.
- Include the full names of all group members on your submitted work (so all get credit).

Let Σ = {0,1,+,=} and

ADD = {x=y+z | x,y,z are binary integers and x is the sum of y and z}

- Give 4 strings that belong to the language ADD.
- Use the Pumping Lemma to show that ADD is not regular.