Institutt for Informatikk
Universitetet i Bergen
I 125 - Innføring i Programoversettelse

Voluntary Exercise Set 2 (Gruppeøvelser. 2)

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.