Universitetet i Bergen

I 125 - Innføring i Programoversettelse

1. Clearly
indicate whether each statement below is **True** or **False**, and justify
your answer.

a.)
The regular expression (*ba*
| *b*) * describes the set of all
strings from the alphabet{*a*, *b*} that do not contain two
consecutive *a*'s.

b.)
The regular expression (*a*
(*a* | *b*)* )^{+} describes
the same language as *a* (*a*
| *b*)*.

2. For each regular expression below, either indicate it that represents the same language as that accepted by the DFA below, or prove that it does not represent the same language. (An easy way to prove that it does accept the same language is to give either a string that is accepted by the DFA but not by the regular expression or a string that is accepted by the regular expression but is not accepted by the DFA.)

a.) *a*^{+}*b* |
*b*^{+}*a*

b.) (*a* |
*b*)*

c.) (*aa***b* |
*bb***a*)(*a* |
*b*)*

d.) *a*^{+}*ba** |
*a*^{+}*bb** |
*b*^{+}*ab** |
*b*^{+}*aa**

e.) (*a* |
*b*) (*a** |
*b**) (*b* |
*a*) (*a* |
*b*)*

f.) (*a*^{+}*b* |
*b*^{+}*a*)(*a* |
*b*)*

3. Exercise 2.12 on page 92 of the text.

4. Use subset construction to convert the following NFA to an equivalent DFA. Assume the transitions without labels are e-transitions.

5. Exercise 2.16 on page 92 of the text.

6. During
the Lecture on 5 September we considered the set of all strings drawn from the
alphabet {*a*, *b*, *c*, *d*} that start with either the
substring *ab* or the substring *cd*. We saw that the regular expression (*ab* | *cd*) (*a*
| *b* | *c* | *d*)* describes
this language. We also saw that a smart
implementation of Thompson`s construction would come up with the following NFA,
where all arcs without any labels correspond to a e-transitions.

a.) Use the subset construction to construct an equivalent DFA.

b.) Apply the state minimization algorithm to convert your DFA for part (a) into a DFA with a minimum number of states.

7. Exercise 2.17 on page 93 of the text.