Examples:
(i) ∅ is a regular language (by rule (a))
(ii) L = {a, ab} is a language over Σ = { , }
a b because, both {a} and {b}
are regular languages by rule (b). By rule (d) it follows that
{ } { } { }
a
b
ab
o
=
is a regular language. Using rule (c), we see that
{ } { }
a
ab L
∪
= is a regular language.
(iii) The language over the alphabet {0,1} where strings contain an
even number of 0’s can be constructed by
(1
*
((01
*
)(01
* ))
*
)
or simply 1
* (01
* 01
* )
* .
1.4.2 Reg u lar Expres sions
Regular expressions were designed to represent regular languages with a
mathematical tool, a tool built from a set of primitives and operations.
This representation involves a combination of strings of symbols from
some alphabet Σ, parantheses and the operators + ⋅
, , and *.
A regular expression is obtained from the symbol {a, b, c}, empty string ∈,
and empty-set ∅ perform the operations + ⋅
, and * (union, concatenation and
Kleene star).
Examples
0 + 1 represents the set {0, 1}
1 represents the set {1}
0 represents the set {0}
(0 + 1) 1 represents the set {01, 11}
(
) (
)
a b b c
+ ⋅ + represents the set {ab, bb, ac, bc}
(0 + 1)
* = ∈ + (0 + 1) + (0 + 1) (0 + 1) + LL = Σ
*
(
)
(
) (
)
{ }
*
*
0 1
0 1 0 1
+
= +
+
=
=
−
+
+
Σ
Σ
ε
1.4.3 Build ing Reg u lar Expres sions
Assume that Σ = { , , }
a b c
Zero or more: a
* means “zero or more a’s”,
To say “zero or more ab’s,” i.e., {λ, ,
,
}
ab abab KK you need to say
(ab)*.
One or more: Since a
* means “zero or more a’s”, you can use aa
* (or
equivalently a
* a) to mean “one or more a’s”. Similarly to describe ‘one or
more ab’s”, that is {ab, abab, ababab, KK}, you can use ab (ab)*.
Zero or one: It can be described as an optional ‘a’ with (a + λ).
DFA and NFA
81