Description
-
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 = 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
