Information Technology Reference
In-Depth Information
Ta b l e 6 . 1 1
Regular expressions
)
∗
a
∗
(
c
+
b
)
(
a
(
b
+
c
)
∗
(
ab
)
∗
+(
ac
)
∗
(
a
+
ab
)
∗
c
((
a
+
ab
)
∗
c
+
bb
)
∗
aabcbb
ab
Fig. 6.4
Two equivalent automata recognizing
L(
a
(
b
+
c
)
∗
)
Ta b l e 6 . 1 2
Patterns of languages of types 1 or 2
a
n
b
2
n
a
n
b
n
+
3
(
aba
)
n
a
n
b
n
a
m
a
n
b
n
a
n
a
n
b
n
a
n
b
n
a
n
b
m
a
n
+
m
are closed with respect to the sum. In fact. given a grammar
G
1
for a language
L
1
and
a grammar
G
2
for a language
L
2
it is easy to provide a grammar, generating
L
1
+
L
2
,
with the lowest type among those of
G
1
and
G
2
. The class
REG
is boolean (closed
with respect to sum, intersection, and complementation). An important result of late
1980s has proved that also
CS
is boolean. However,
CF
is not boolean because it
is not closed with respect to intersection. In fact,
a
n
b
n
c
m
and
a
n
b
m
c
m
are patterns
