(ii) Consider the NFA to be a generalised transition graph, which is
just like an NFA except that the edges may be labeled with
arbitrary regular expressions. Since the labels on the edges of an
NFA may be either λ or members of each of these can be
considered to be a regular expression.
(iii) Removes states one by one from the NFA, relabeling edge as you
go, until only the initial and the final state remain.
(iv) Read the final regular expression from the two state automaton
that results.
The regular expression derived in the final step accepts the same language
as the original NFA.
Ì Exam ple 1.4.1: Represent the following sets by regular expression
(a) { , }
∧ ab
(b) { , , ,
}
1 11 111 KK
(c) { , , , }
ab a b bb
Solu tion
(a) The set { , }
∧ ab is represented by the regular expression ∧ + ab
(b) The set { , , ,
}
1 11 111 KK is got by concatenating 1 and any element
of {1}
* . Therefore 1(1)
* represent the given set.
(c) The set { , , , }
ab a b bb represents the regular expression
ab a b bb
+ + + .
Ì Exam ple 1.4.2: Obtain the regular expressions for the following sets:
(a) The set of all strings over {a, b} beginning and ending with ‘a’.
(b) { , , ,
}
b b b
2
5
8 KK
(c) {
|
}
a
n
n
2 1
0
+
>
Solu tion
(a) The regular expression for ‘the set of all strings over {a, b}
beginning and ending with ‘a’ is given by:
a (a + b)
* a
(b) The regular expression for { , , ,
}
b b b
2
5
8 KK is given by:
bb (bbb)
*
(c) The regular expression for {
|
}
a
n
n
2 1
0
+
> is given by:
a (aa)
*
84
Theory of Automata, Formal Languages and Computation