Any string at all: To describe any string at all (with Σ = { , , }
a b c you can use
(a + b + c)
* .
Any nonempty string: This is written any character from Σ = { , , }
a b c followed
by any string at all: (
) (
)
*
a b c a b c
+ +
+ +
Any string not containing ..........: To describe any string at all that does not
contain an ‘a’ (with Σ = { , , }
a b c ), you can use (b + c)
* .
Any string containing exactly one ........: To describe any string that contains
exactly one ‘a’ put “any string not containing an a”, on either side of the ‘a’
like: (
) (
)
*
*
b c a b c
+
+ .
1.4.4 Lan guages defined by Reg u lar Expres sions
There is a very simple correspondence between regular expressions and the
languages they denote:
Reg u lar expres sion
L (Reg u lar Expres sion)
x, for each x ∈ Σ
{x}
λ
{λ}
∅
{ }
( )
r 1
L r
( )
1
r 1
∗
( ( ))
*
L r 1
r r
1 2
L r L r
( ) ( )
1
2
r r
1
2
+
L r
L r
( )
( )
1
2
∪
1.4.5 Reg u lar Expres sions to NFA
(i) For any x in Σ, the regular expression denotes the language {x}.
The NFA (with a single start state and a single final state) as
shown below, represents exactly that language.
(ii) The regular expression λ denotes the language {λ}that is the
language containing only the empty string.
82
Theory of Automata, Formal Languages and Computation
x
NFA for x
λ
NFA for λ