Tutorial 1 solution

COMPILER CONSTRUCTION

Week 2 Tutorial Solutions

Regular Expressions, NFA and DFA

1. Let ∑ = {a,b}. Write regular expressions for the languages over ∑ that contain:

a. All strings.

(a|b)*

b. The empty string.

∈

c. The string abb.

abb

d. The strings ba and aba.

ba|aba

e. All strings beginning with ab.

ab(a|b)*

f. All strings beginning with a a and ending with a b.

a(a|b)*b

g. All strings that contain exactly two a’s.

b*ab*ab*

h. All strings in which every a is followed by a b.

(b|ab)*

7 0 1 2

3 4

5 6

∈

∈

∈ ∈

∈

a

b

a ∈

8

∈

0 10

1 2

5

6 7

3 4 8 9

a a

2. Construct nondeterministic finite automata (NFA) from the following regular

expressions:

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

• ∈ ∈

∈ ∈

/ \

| |

/ \ / \

a b a b

∈ ∈ ∈

∈

b b

b. a(a|b)+

•

/ \

a +

|

/ \

a b