Automata Theory

Answers to selected exercises 3

John C Martin: Introduction to Languages and the Theory of Computation
Fourth edition

Jetty Kleijn, Marcello Bonsangue, Rudy van Vliet

Fall 2024

3.1 a. r = b∗ (ab)∗ a∗ : the word aab is not in the language, defined by r,

since every a should be followed by a b or belong to a suffix of a’s. Note
that Λ, a, b, and all words of length 2 are in the language, defined by r. So,
aab is of minimal length.
Another example is abb: every b should be preceded by a a unless it is part
of a prefix of b’s.
b. r = (a∗ + b∗ )(a∗ + b∗ )(a∗ + b∗ ): the words abab and baba are examples
of words not belonging to the language defined by r, because r allows only
a maximum of two a-b or b-a changes in a word when reading it from left
to right. Verify that there are no shorter words (i.e. of length ≤ 3) not
belonging to the language of r.
c. r = a∗ (baa∗ )∗ b∗ : the word bba does not belong to the language defined by
r, because every occurrence of b should be followed by at least one a unles
it belongs to a suffix of b’s. Verify that all words of length ≤ 2 belong to
the language.
d. r = b∗ (a + ba)∗ b∗ : the word abba does not belong to the language of r,
because that requires that a b can only be followed by a b if it belongs to a
prefix or suffix consisting of b’s. Verify that all words of length ≤ 3 belong
to the language.

3.3 a. r(r∗ r + r∗ ) + r∗ = r∗ .
b. (r + Λ)∗ = r∗ .
c. The expression (r + s)∗ rs(r + s)∗ + s∗ r∗ denotes all words that
contains at least once rs (i.e. the expression (r + s)∗ rs(r + s)∗ ) or do not
contains any occurrence of rs at all (i.e. the expression s∗ r∗ ). This is thus
equivalent to (r + s)∗ .

1
extra 1 The expression (r + s + rs + sr)∗ can be simplified in (r + s)∗
extra 2 The expression (r(r + s)∗ )+ can be simplified in r(r + s)∗

• Prove the formula

(aa∗ bb∗ )∗ = Λ + a(a + b)∗ b

To be proved: the regular expressions (aa∗ bb∗ )∗ and Λ + a(a + b)∗ b define
the same language, i.e., ({a}+ {b}+ )∗ = {Λ} ∪ {a}{a, b}∗ {b}.
Note that Λ occurs both on the left side and on the right side.
Every non-empty string from the first language begins with a and ends with
b, and thus is an element of {a}{a, b}∗ {b}.
Now consider a string w from {a}{a, b}∗ {b}, so w = axb for some x ∈ {a, b}∗ .
Let n be the number of times that string w switches from a to b (so w con-
tains n substrings ab).
We use induction on n to prove that w ∈ ({a}+ {b}+ )∗ .
Basis: If n = 1, then w ∈ {a}{a}∗ {b}∗ {b} = {a}+ {b}+ , and thus w is an
element of the first language.
Induction hypothesis: Let k ≥ 1, and suppose that all strings from
{a}{a, b}∗ {b} that switch k times from a to b are also elements of the first
language.
Induction step: Now let n = k+1. Then w = yz for some y ∈ {a}{a}∗ {b}∗ {b}
and z ∈ {a}{a, b}∗ {b} where string z switches k times from a to b.
By the induction hypothesis, z is an element of ({a}+ {b}+ )∗ , so
w ∈ {a}{a}∗ {b}∗ {b}({a}+ {b}+ )∗ ⊆ ({a}+ {b}+ )∗ .

3.6 a. (w)∗ (z)∗

b. (w)∗ a(w + z)∗
c. (w + z)∗ (a + Λ)

3.7 a. b∗ ab∗ ab∗

b. b∗ ab∗ a(a + b)∗ .
c. Λ + b + (a + b)∗ a + (a + b)∗ bb
e. (b + ab)∗ (Λ + a) and (Λ + a)(b + ba)∗
f. b∗ (ab∗ ab∗ )∗
g. (b + ab)∗ (Λ + a + aa)(b + ba)∗
h. b∗ (abbb∗ )∗
k. (a + ba)∗ b∗ .
l. (a + b)∗ bab(a + b)∗ aba(a + b)∗ + (a + b)∗ aba(a + b)∗ bab(a + b)∗ + (a +
b) baba(a + b)∗ + (a + b)∗ abab(a + b)∗ .
∗

The two substrings (in either order) either do not or do overlap.

2
 m. (b + a(aa + bb)∗ (ab + ba))(aa + bb + (ab + ba)(aa + bb)∗ (ab + ba))∗
The first part checks a minimum string with an odd number of b’s and
an even number of a’s. After that the strings can be extended as much as
we want with a string of even number of a’s and b’s .
n. (aa + bb)∗ (ab + ba)(aa + bb + (ab + ba)(aa + bb)∗ (ab + ba))∗
The first part checks a minimum string with an odd number of b’s and
an odd number of a’s. After that the strings can be extended as much as
we want with a string of even number of a’s and b’s .
n. Alternative solution, with a different expression for strings with both an
even number of a’s and an even number of b’s:
(aa + bb)∗ (ab + ba)(aa + bb)∗ ((ab + ba)(aa + bb)∗ (ab + ba)(bb + aa)∗ )∗

3.10 We define the reverse function rev to assign to each string x its reversal
(mirror image) xr .
Formally, given an alphabet Σ, we define rev: Σ∗ → Σ∗ recursively by:
rev(Λ) = Λ (no change)
rev(xa) = arev(x) for x ∈ Σ∗ , a ∈ Σ (last letter first, reverse the rest)
rev(x) may be abbreviated as xr .
For a language L we use Lr to denote the language consisting of the reversals
of the words from L, thus Lr = {xr | x ∈ L}.
a. Consider the regular expression e = (aab + bbaba)∗ baba defining the reg-
ular language ||e||. Then the language ||e||r can be defined by the regular
expression er = abab(baa + ababb)∗ ; thus ||er || = ||e||r .
b. Let us use rrev to denote the function which ‘reverses’ regular expres-
sions (in the sense that it yields a regular expression with a reversed seman-
tics). We can recursively define rrev as follows: rrev(∅) = ∅; rrev(Λ) = Λ;
rrev(a) = a for all a ∈ Σ.
and for the composite elements:
if e1 and e2 are regular expressions, then rrev(e1 +e2 ) =rrev(e1 )+rrev(e2 );
rrev(e1 e2 ) =rrev(e2 )rrev(e1 ); and rrev(e∗1 ) = (rrev(e1 ))∗ .
Now we have to prove that this rrev has the property ||rrev(e)|| = ||e||r .
This is proved by induction on the structure of e:
e = ∅: then ||rrev(∅)|| = ||∅|| = ||∅||r ;
e = Λ: then ||rrev(Λ)|| = ||Λ|| = ||Λ||r ;
e = a: then ||rrev(a)|| = ||a|| = ||a||r .
Induction step, assuming that ||rrev(e1 )|| = ||e1 ||r and ||rrev(e2 )|| = ||e2 ||r :
e = e1 + e2 : then
||rrev(e1 + e2 )|| = ||rrev(e1 )+rrev(e2 )|| = ||rrev(e1 )|| ∪ ||rrev(e2 )|| =
(induction) ||(e1 )||r ∪ ||(e2 )||r = (||e1 || ∪ ||e2 ||)r = ||e1 + e2 ||r ;
e = e1 e2 : then

3
||rrev(e1 e2 )|| = ||rrev(e2 )rrev(e1 )|| = ||rrev(e2 )|| · ||rrev(e1 )|| =
(induction) ||(e2 )||r ||(e1 )||r = (||(e1 )|| · ||(e2 )|)|r = ||e1 e2 ||r ;
e = e∗1 : then
||rrev(e∗1 )|| = ||(rrev(e1 ))∗ || = ||rrev(e1 )||∗ =
(induction) (||e1 ||r )∗ = (||e1 ||∗ )r = ||e∗1 ||r .
c. It follows from b. that the language Lr is regular whenever the language
L is regular: we have seen that L = ||e|| implies that Lr = ||rrev(e)|| and
that rrev(e) is a regular expression follows immediately from the definition
of rrev as given above.

3.18 See Figure 3.34.

a. We determine δ ∗ (1, aba). First observe that δ ∗ (1, Λ) = Λ({1}) = {1};
then δ ∗ (1, a) = Λ( r∈δ∗ (1,Λ) δ(r, a) = Λ(δ(1, a)) = Λ({2}) = {2, 3}. This
S

means that processing symbol a from the initial state leads to state 2 or
state 3.
We add b: δ ∗ (1, ab) = Λ(δ(2, b) ∪ δ(3, b)) = Λ(∅ ∪ {3, 4}) = {3, 4, 5} and so
after ab we are in either state 3 or state 4 or state 5.
Finally we process another a: δ ∗ (1, aba) = Λ(δ(3, a) ∪ δ(4, a) ∪ δ(5, a)) =
Λ({4} ∪ {4} ∪ ∅) = Λ({4}) = {4, 5}. Thus after reading aba we are in state
4 or in state 5 and since 5 is an accepting state, aba is accepted by M .
b. abab is not accepted: from a. we know that δ ∗ (1, aba) = {4, 5}. Thus
δ ∗ (1, abab) = Λ(δ(4, b) ∪ δ(5, b)) = Λ(∅) = ∅. Not only is there no accepting
state for abab, it cannot even be completely processed!
c. aaabbb is accepted by M (check!).

3.21, 3.23: as in 3.18.

3.22
a. Λ({2, 3}) = {2, 3, 5}.
b. Λ({1}) = {1, 2, 5}.
d. To determine δ ∗ (1, ba) = first observe that δ ∗ (1, Λ) = Λ({1}) = {1, 2, 5}
(see above item b.). We thus have δ ∗ (1, b) = Λ( p∈δ∗ (1,Λ) δ(p, b)) = Λ(δ(1, b)∪
S

δ(2, b) ∪ δ(5, b)) = Λ({6, 7}) = {1, 2, 5, 6, 7}. Finally we obtain δ ∗ (1, ba) =
Λ( p∈δ∗ (1,b) δ(p, a)) = Λ(δ(1, a)∪δ(2, a)∪δ(5, a)∪δ(6, a)∪δ(7, a)) = Λ({3, 5}) =
S

{3, 5}.
S 
3.24 δ ∗ (q, σ) = Λ δ(p, σ) = = δ(q, σ) .
S
p∈δ ∗ (q,Λ) p∈{q} δ(p, σ)

3.25 If M = (Q, Σ, q0 , A, δ) is an FA accepting a language L, then Σ∗ − L,

the complement of L is accepted by the FA M ′ = (Q, Σ, q0 , Q − A, δ) ob-
tained by interchanging the role of accepting and non-accepting states.

4
This construction however does not work for nondeterministic automata,
because a word may have (at the same time) an accepting computation, a
computation not leading to an accepting state, and an incomplete compu-
tation (which does not allow the word to be fully processed).
Here is an example of an NFA M which does not accept the word 10,
because the automaton cannot process a 0 after a 1. Interchanging the
accepting/non-accepting property does not work: also the resulting M ′ will
not be able to read 10; and so 10 6∈ L(M ′ ). Since 10 is also not in L(M ), it
follows that L(M ′ ) is not the complement of L(M ).
NFA M NFA M ′
0 1 0 1
1 1

As another example consider the NFA M given by its transition diagram:

NFA M NFA M ′
1 1
1 1

1 1
0 0

M accepts 1, but note that δ ∗ (q0 , 1) consists of two states, one accepting and
one non-accepting. Consequently, the NFA M ′ obtained by interchanging
accepting and non-accepting states, also accepts 1. Hence L(M ′ ) is not the
complement of L(M ).
As another example, a string may be accepted in some accepting state
which has a Λ-transition to a non-accepting state. Then the string again
has both an accepting computation and a non-accepting computation.

• Similar to the previous problem, we consider adapting Theorem 2.15 to the

case of NFAs without Λ-transitions. For i = 1, 2, let M1 = (Qi , Σ, qi , Ai , δi ),
and let M = (Q1 × Q2 , Σ, (q1 , q2 ), A, δ), where A is defined as in the theorem
for each of the three cases and δ still needs to be defined.
If M1 and M2 are FAs, the appropriate definition of δ is to use the
formula δ((p, q), σ) = (δ1 (p, σ), δ2 (q, σ)). If M1 and M2 are NFAs, let us
define δ((p, q), σ) = δ1 (p, σ) × δ2 (q, σ). (This says for example that if from
state p M1 can reach either p1 or p2 on input σ, and from state r M2 can
reach either r1 or r2 on input σ, then M can reach any of the four states
(p1 , r1 ), (p1 , r2 ), (p2 , r1 ), (p2 , r2 ) from (p, r) on input σ.)

5
 Do the conclusions of the theorem still hold in this more general situ-
ation? Answer in each of the three cases (union, intersection, difference),
and give reasons for your answer.
Let M1 = (Q1 , Σ, q1 , A1 , δ1 ) and M2 = (Q2 , Σ, q2 , A2 , δ2 ) be two NFAs
without Λ-transitions. Their product NFA M is defined as M = (Q1 ×
Q2 , Σ, (q1 , q2 ), A, δ) with δ((p1 , p2 ), σ) = δ1 (p1 , σ) × δ2 (p2 , σ). Note that
δ((p1 , p2 ), σ) = ∅ whenever δ(p1 , σ) = ∅ or δ(p2 , σ) = ∅. Similar to the de-
terministic case, we define the set of accepting states A as
either Au = (A1 × Q2 ) ∪ (Q1 × A2 ) for union (L(M1 ) ∪ L(M2 ))
or Ai = A1 × A2 for intersection (L(M1 ) ∩ L(M2 ))
or Ad = A1 × (Q2 − A2 ) for difference (L(M1 ) − L(M2 )).
Now the question is whether these constructions are correct:
union: NO, since a word which does not have a complete computation in
one of the automata M1 and M2 , will not have a complete computation in
M and hence cannot be accepted by M even if the other one of M1 , M2
would accept it. Solution: add a sink state (to M1 and M2 ).
intersection: YES, because a word has an accepting computation in M with
Ai as its set of accepting states if and only if it has an accepting computation
in both M1 and M2 .
difference: NO, if a word is accepted by M1 and this word has a (com-
plete) non-accepting computation in M2 , then it will be accepted by M
with accepting state set Ad , even though it may be the case that it also
has an accepting computation in M2 and hence is not in L(M1 ) − L(M2 ).
For a word x accepted by M1 and such that it is never completely read by
M2 , the product NFA does not have a complete computation either. Thus
x ∈ L(M1 ) − L(M2 ), but x will never lead to an accepting state in Ad . (See
also the previous exercise.)

3.26 For all q ∈ Q: δ ∗ (q, Λ) = Λ({q}) ;

for all q ∈ Q, σ ∈ Σ en y ∈ Σ∗ :

δ ∗ (q, σy) = δ ∗ (p2 , y)

[

p2 ∈ δ(p1 , σ) with p1 ∈ Λ({q})

• Suppose M is an NFA accepting L ⊆ Σ∗ . Describe how to modify M to

obtain an NFA recognizing rev(L) = {xr | x ∈ L}.
Let M = (Q, Σ, q0 , A, δ) be an NFA accepting the language L. We modify M
in such a way that an NFA M ′ results that recognizes rev(L) = {xr | x ∈ L},
the reversal of L. (See also Exercise 3.10.)
First we reverse all the arrows of M : if q ∈ δ(p, σ) for some σ ∈ Σ ∪ {Λ},

6
then we have p ∈ δ ′ (q, σ).
The (only) accepting state of M ′ is q0 , the initial state of M .
We need a new initial state for M ′ ; therefore we introduce a new state
p0 6∈ Q. From p0 all computations in M ′ start by going to an original
accepting state with a Λ-transition: we include in δ ′ for each accepting state
of M , a Λ-transition from p0 to that state.
It is now rather easy to see that L(M ′ ) = rev(L): For any sequence of
transitions in M from q0 to an accepting state qf ∈ A, we have a path
in M ′ which starts in p0 with a Λ-transition to qf , and then follows the
original path in reverse ending with q0 , which is the accepting state of M ′ .
Conversely, for any sequence of transitions in M ′ leading from p0 to q0 , the
reverse sequence, apart from the Λ-transition with which we leave p0 , is a
path in M implying that the reversed string is accepted by M .

3.33 Consider the language L = {Λ, a}. Since Λ ∈ L, any NFA accepting L
will have its initial state as one of its accepting states. Since a is an element
of L, an NFA accepting L will have a transition for a from its initial state to
an accepting state. If this accepting state were the same state as the initial
state, then the automaton accepts all words from {a}∗ and not just a0 = Λ
and a. We conclude that any NFA accepting L has at least two distinct
accepting states.

3.34 Yes, every language that does not contain Λ and can be accepted by an
NFA can be accepted by an NFA with only one accepting state. (Compare
with Exercise 3.33.)
Suppose that we are given an NFA M = (Q, Σ, q0 , A, δ) with 0 or 2 or more
accepting states, different from q0 . Then we add a new (accepting) state t
and for every state p, symbol a and original accepting state q of M such
that q ∈ δ(p, a), we add a new arrow from p to t labeled with a. This yields
an NFA M ′ = (Q ∪ {t}, Σ, q0 , {t}, δ ′ ) which accepts L(M ): the last arrow
in every accepting path of M can be simulated in M ′ with a cooresponding
arrow to t in M ′ ; conversely, for every accepting computation in M ′ (thus
leading to t), there is an accepting computation in M leading to one of the
original accepting states.
NFA M NFA M ′
b
a
b
b a a
t
a a, b
b
b

7
• Let M = (Q, Σ, q0 , A, δ) be an FA.
a. Show that if all states other than q0 from which no element of A can
be reached are deleted, then what remains is an NFA accepting the same
language.
b. Show that if all states not reachable from q0 are deleted and all states
other than q0 from which no element of A can be reached are deleted, then
what remains is an NFA accepting the same language.
M = (Q, Σ, q0 , A, δ) is an FA. Consider an arbitrary accepting sequence of
transitions q0 −→a1 q1 −→a2 q2 . . . qn−1 −→an qn . Thus n ≥ 0, qn ∈ A and
each ai ∈ Σ.
a. Clearly, if a state appears in a successful accepting path of M then there is
at least one accepting state reachable from it. Consequently we can remove
all (non-initial) states from which no accepting state is reachable without
affecting the successful paths, that is without affecting the language. The
resulting automaton has the same initial state as M and it may be non-
deterministic since it is no longer necessarily the case that for every state p
and every symbol a a next state is defined.
b. Similarly, all states appearing in a successful path are reachable from q0
and hence all non-reachable states can be removed leading to an NFA that
accepts the same language. This can be combined with the strategy from
a., leading to an NFA in which every state is reachable from q0 and in which
from every non-initial state an accepting state can be reached.

3.37 See Figure 3.36. Use the algorithm from the lectures to obtain for each
NFA M an NFA M ′ without -Λ transitions accepting the same language.
a. In the table below, the first four columns describe the transition function
of M . Its initial state is 1 and it has one accepting state: 4. As a useful
extra we then compute Λ({q}), the set consisting of all states that can be
reached from q using only Λ-transitions. Next we compute the transitions
of M ′ , for each state q and symbol σ ∈ {a, b}, using the formula δ ′ (q, σ) =
S
r∈Λ(q) δ(r, σ).
Now we have the transitions of M ′ in the last two columns. Its initial state
is again 1. As accepting states it has now 4 (just like M ), but also the inital
state 1, since Λ({1}) ∩ {4} = {4} = 6 ∅ !!!

8
 q δ(q, Λ) δ(q, a) δ(q, b) Λ({q}) δ ′ (q, a) δ ′ (q, b)
1 {4} ∅ {2} {1, 4} ∅ {2, 5}
2 ∅ {3} ∅ {2} {3} ∅
3 ∅ ∅ {1} {3} ∅ {1}
4 ∅ ∅ {5} {4} ∅ {5}
5 ∅ {4} ∅ {5} {4} ∅

Draw M ′ .

3.38 In Figure 3.37 several NFAs are given.

a. NFA M has initial state 1 and accepting state 3, its transition function
is given in the following table.
a b
1 {1, 2} {1}
2 ∅ {3}
3 ∅ ∅

The subset construction yields an FA with 3 reachable states: {1} is its

initial state and {1, 3} is its (only) accepting state. The transition function
is given below in a table (draw the transition diagram for yourself).
a b
{1} {1, 2} {1}
{1, 2} {1, 2} {1, 3}
{1, 3} {1, 2} {1}

3.39 If there is an NFA accepting L with k states, then there is also an NFA
without Λ-transitions accepting L with k states. By the subset construction,
there is an FA accepting L with no more than 2k states. Consequently, if
every FA accepting L has at least n states than there is no NFA accepting L
with fewer than 2 log n states. That is, every NFA accepting L has at least
⌈2 log n⌉ states.

3.44 a. We add a new initial state qi 6∈ Q and a Λ-transition δ(qi , Λ) = {q0 }.

All the rest remains unchanged.
b. We add a new single accepting state qf 6∈ Q and a Λ-transition δ(q, Λ) =
{qf } from every q ∈ A. All the rest remains unchanged.

3.46 The construction proposed does not work: take two automata M1 =
({q1 }, {a, b}, q1 , {q1 }, δ1 ) and M2 = ({q2 }, {a, b}, q2 , {q2 }, δ2 ), with δ1 (q1 , a) =

9
 {q1 }, and δ2 (q2 , a) = {q2 }. Then L(M1 ) = {an |n ≥ 0} and L(M2 ) = {bn |n ≥
0}. In the new automata Mu we would have a path δ ∗ (q1 , aaλ) bringing to
an accepting state (namely q2 ), but aab 6∈ L(M1 ) ∪ L(M2 ).

3.51 a See Figure 3.40 (a).

r0 (i, j) j = 1 2 3
i=1 Λ b a
2 a Λ b
3 b a Λ

r1 (i, j)
r1 (i, j) j=1 2 3
simplified j = 1 2 3
i = 1 Λ + ΛΛ∗ Λ b + ΛΛ∗ b a + ΛΛ∗ a
i=1 Λ b a
2 a + aΛ∗ Λ Λ + aΛ∗ b b + aΛ∗ a
2 a Λ + ab b + aa
3 b + bΛ∗ Λ a + bΛ∗ b Λ + bΛ∗ a
3 b a + bb Λ + ba
r2 (i, j) j=1 2 3
i=1 Λ + b(Λ + ab)∗ a b + b(Λ + ab)∗ (Λ + ab) a + b(Λ + ab)∗ (b + aa)
2 a + (Λ + ab)(Λ + ab)∗ a Λ + ab + (Λ + ab)(Λ + ab)∗ (Λ + ab) b + aa + (Λ + ab)(Λ + ab)∗ (b + aa)
3 b + (a + bb)(Λ + ab)∗ a a + bb + (a + bb)(Λ + ab)∗ (Λ + ab) Λ + ba + (a + bb)(Λ + ab)∗ (b + aa)
r2 (i, j)
simplified j=1 2 3
i=1 Λ + b(ab)∗ a b(ab)∗ a + b(ab)∗ (b + aa)
2 (ab)∗ a (ab)∗ (ab)∗ (b + aa)
3 b + (a + bb)(ab) a (a + bb)(ab) Λ + ba + (a + bb)(ab)∗ (b + aa)
∗ ∗

r3 (1, 3) = a + b(ab)∗ (b + aa)

+ (a + b(ab)∗ (b + aa))(Λ + ba + (a + bb)(ab)∗ (b + aa))∗ (Λ + ba + (a + bb)(ab)∗ (b + aa))
= (a + b(ab)∗ (b + aa))(ba + (a + bb)(ab)∗ (b + aa))∗

For simplifying the expressions we used the following equalities, for arbitrary
regular expressions r, r1 , r2 :

Λ∗ = Λ
Λr = rΛ = r
r+r = r
(Λ + r)∗ = r∗
r∗ (Λ + r) = (Λ + r)r∗ = r∗

10
 r1 + r1 (r2 )∗ = r1 (r2 )∗
r1 + (r2 )∗ r1 = (r2 )∗ r1
Λ + r∗ = r∗
r + r∗ = r∗

3.51 c See Figure 3.40 (c). We use the state removal method of Brzozowski
and McCluskey to derive for the depicted automata a corresponding regular
expression.
First we add a new initial state q0 without incoming transitions and a new
(the only) final state qf without outgoing transitions in such a way that the
resulting NFA accepts the same language (see exercise 3.44). At the same
time we combine with + the labels of parallel edges into a single regular
expression.
1 a, b 2 Λ 1 a+b 2
Λ
q0
a b a, b a b a+b qf
a, b a+b Λ
4 3 4 3

Now we remove state 4. Before deleting 4, we consider the transitions from

3 to 4 and from 4 to 1 and 2. This leads to the introduction of an arc labeled
with (a + b)a from 3 to 1 and an arc labeled with (a + b)b from 3 to 2.

Λ 1 a+b 2
Λ
q0 (a + b)b
a+b qf
(a + b)a
Λ
3

Then state 1 is removed. This leads to the introduction of an arc labeled

with Λ(a + b) from q0 to 2 and an arc labeled with (a + b)a(a + b) from 3
to 2. The latter is combined using + with the label (a + b)b of the already
existing arc from 3 to 2.

11
 Λ(a + b) 2
Λ
q0
a+b qf
(a + b)b + (a + b)a(a + b)
Λ
3

Then state 3 is removed. This leads to the introduction of an arc labeled

with (a + b)Λ from 2 to qf which is combined with the existing parallel arc
labeled with Λ. Also an arc from 2 to 2 is added which is labeled with
(a + b)((a + b)b + (a + b)a(a + b)), a combination of the label of the arc from
2 to 3 and that of the arc from 3 to 2.
(a + b)((a + b)b + (a + b)a(a + b))

Λ(a + b) 2
Λ + (a + b)Λ
q0
qf

Finally, we remove state 2 and find a regular expression for L(M ).

Λ(a + b)((a + b)((a + b)b + (a + b)a(a + b)))∗ (Λ + (a + b)Λ)

qf
q0

L(M ) = {a, b}({a, b}({a, b}{b} ∪ {a, b}{a}{a, b}))∗ {Λ, a, b}.

Version of 13 December 2024. Feel free to mention any errors in these solutions at
rvvliet@liacs.nl

12