The state table corresponding to the DFA is derived by using subset
construction. State table for DFA is as shown below.
a
b
[q 0 ]
[q 1 ]
[q 2 ]
[q 1 ]
∅
[q 3 ]
[q 2 ]
[q 3 ]
∅
[q 3 ]
∅
∅
∅
∅
∅
The DFA is as shown above.
1.4 REGULAR EXPRESSION
1.4.1 Reg u lar Lan guages
The regular languages are those languages that can be constructed from the
“big three” set operations viz., (a) Union (b) Concatenation (c) Kleene star.
A regular language is defined as follows.
Definition: Let Σ be an alphabet. The class of “regular languages” over Σ is
defined inductively as follows:
(a) ∅ is a regular language
(b) For each σ
σ
∈ Σ, { } is a regular language
(c) For any natural number n ≥ 2 if L L
L n
1
2
, , KK
are regular
languages, then so is L
L
L n
1
2
∪ ∪
∪
K K
.
(d) For any natural number n ≥ 2, if L L
L n
1
2
, , KK
are regular
languages, then so is L L
L n
1
2
o o K K o .
(e) If L is a regular language, then so is L
* .
(f) Nothing else is a regular language unless its construction follows
from rules (a) to (e).
80
Theory of Automata, Formal Languages and Computation
[] q 0
a
∅
a
b
[] q 1
[] q 2
[] q 3
a
b
a,b
b
b
a