Problem Set 2—Regular Expressions

Purpose

This problem set reinforces your understanding of regular expressions. In particular, it focuses on using regular expressions to describe languages, and on the equivalence of the languages of regular expressions and finite automata.

Background

This problem set is based on material in section 1.3 of our textbook. We discussed this material in class starting on February 1. This exercise also relies indrectly on constructions related to closure properties of regular languages. This material is at the end of section 1.2 of the textbook, and was discussed in the January 29 class.

Activity

Solve each of the following problems.

Problem 1

Problem 1.20c in our textbook (give 2 examples of strings that are members of the language generated by a*∪b* and 2 examples of strings that are not in this language).

Problem 2

Exercise 1.8, parts a and e in our textbook (give regular expressions for the languages over {0,1} whose members (a) begin with a 1 and end with a 0, and (e) start with 0 and have odd length or start with 1 and have even length).

Problem 3

Exercise 1.19a and c in our textbook (use the construction from Lemma 1.55 to (a) construct an NFA that recognizes (0∪1)*000(0∪1)*, and (c) construct an NFA that recognizes ∅*).

Problem 4

Exercise 1.21b in our textbook (convert a certain 3-state DFA to a regular expression; see textbook for details).

Problem 5

Problem 1.31 in our textbook (show that if L is regular, then L^R, the set of all strings whose reverses are in L, is regular). Hint: do the proof in terms of regular expressions, not finite automata.

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.