## Description

1. grep and many other software implementations of regular expressions include the question mark , `?’, as a special symbol which marks the preceding expression as optional. For example, the regular expression dog(gy)?

matches the strings `dog’ and `doggy’.

Let REQ be an extension of our familiar language of regular expressions

with the question mark operator added. We will formally dene the set

REQ by extending the denition of RE (denition 7.6 in the Vassos course

notes) to add the following induction step: If R 2 REQ, then (R)? 2

REQ.

(a) Denition 7.7 in the Vassos course notes is a recursive denition of

the language denoted by a regular expression R 2 RE. Give an

extended version of this denition for REQ.

(b) Show that REQ has no more expressive power than RE, by proving

the following statement: 8R1 2 REQ; 9R2 2 RE;L(R2) = L(R1).

Your proof should use structural induction.

2. Given a DFSA M = (Q; ; ; s; F), we will say that M is frumious if the

following is true:

8a 2 ; 9q1 2 Q; 8q2 2 Q; (q2; a) = q1

(a) Give a short English description of what it means for a DFSA to be

frumious.

(b) If M is frumious, what can we say about the language accepted by

M, L(M)?

(c) How many distinct languages over the alphabet f0; 1g can be recognized by frumious DFSAs? Brie y explain your answer.

3. Suppose L is an innite regular language. Does it follow that there exists

a nite language S such that L = SS? If yes, prove it. If no, nd a

counterexample language L and prove that it cannot be formed this way.

1