CSC236
Assignment #3: formal languages
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 de ne the set
REQ by extending the de nition of RE (de nition 7.6 in the Vassos course
notes) to add the following induction step: If R 2 REQ, then (R)? 2
REQ.
(a) De nition 7.7 in the Vassos course notes is a recursive de nition of
the language denoted by a regular expression R 2 RE. Give an
extended version of this de nition 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 in nite 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
