Description
Computational Models
• Read Myhill-Nerode handout in the ecommons resources folder.
• Use the Myhill-Nerode Theorem to prove that the languages in Exercise 1.29 (a and c), page
88 and Problem 1.46 (b and c) page 90, are not regular.
• Prove any language of your choice is regular with the Myhill-Nerode theorem. Could you
have done the proof (of regularity) with the Pumping Lemma?
• Read chapter 2 of the book at least through page 105 2nd ed, 107 3rd ed.
• Exercises 2.3 and 2.4, page 128 2nd ed, 155 3rd ed.
• Give a CFG for the language {x ∈ {a, b}
∗
| x 6= ww for some w ∈ {a, b}
∗}.
Homework Policies: You may study together in small groups and discuss ideas about the
homework problems before composing the solutions. You are expected, however, to write the
solutions yourselves and not copy them from other students or share your solutions with other
students. If you have worked closely with other students on particular problems, then you must
mention the names of the people you have worked with and also the problems on which you worked
together.
1 CMPS 130
