Information Technology Reference
In-Depth Information
based on the definition of the following language, relative to a given automaton
M
=(
A
,
Q
,
τ
,
F
,
q
1
)
with
Q
=
{
q
1
,
q
2
,...,,
q
n
}
L
i
,
j
n
of the strings which produces the state passage of
M
from
q
i
to
q
j
possibly by
passing through
q
1
,
q
2
,...,
q
n
.
Of course, we have:
L
i
,
j
0
⊆
A
moreover, for all
i
,
j
∈
N
, the following equation holds:
∗
L
i
,
j
k
+
1
L
i
,
j
k
L
i
,
k
+
1
k
L
k
+
1
,
k
+
1
k
L
k
+
1
,
j
k
=
+
·
(
)
·
The validity of this equation can be explained if we consider the following example
of chain of state transitions in the automaton
M
, where dots between states denotes
intermediate states among
, and the state
q
k
+
1
occurs three times
(clearly any number of times could be considered):
{
q
1
,
q
2
,...,
q
k
}
q
j
.
Now, for passing from
q
i
to
q
j
, possibly by passing through
q
k
+
1
,therearetwo
possibilities: or
M
does not pass through
q
k
+
1
(term
L
i
,
j
k
in the equation above)
or
M
goes from
q
i
to
q
k
+
1
(term
L
i
,
k
+
1
k
in the equation above) by passing again
from
q
k
+
1
to
q
k
+
1
(two times in the example above) through the other
k
states (term
(
q
i
.........
q
k
+
1
.........
q
k
+
1
.........
q
k
+
1
.........
∗
in the equation above), and finally, from
q
k
+
1
to
q
j
through the other
k
states (term
L
k
+
1
,
j
k
L
k
+
1
,
k
+
1
k
)
=
in the equation above). Therefore, if the final states are
F
,
,...
q
m
q
m
+
1
q
n
, the language recognized by
M
is given by:
L
1
,
m
n
L
1
,
m
+
1
n
L
1
,
n
n
L(
M
)=
+
+
...
+
.
In conclusion, all the equations above show that the language recognized by
M
is obtained by applying regular operations (sum, concatenation, and Kleene star)
starting from finite languages (the proof uses implicitly the principle of induction
given in Sect. 5.8).
Very often grammars and automata corresponding to a given regular expression can
be found in a simple way. However, an interesting problem, which occurs in many
contexts, is the search of “minimal” grammars or automata equivalent to some given
(complex) regular expression (according to some specified notion of size of these
devices). The automaton of Fig. 6.4 provides two equivalent automata recognizing
the (language of) the first regular expression of Table 6.11.
Table 6.11 shows a list of regular expressions, while Table 6.12 shows the pat-
terns (with
n
0) of languages of types 1 or 2. First four languages are of type 2,
while the last three are of type 1. Classes of languages of interest in natural phenom-
ena (forms of developments, complex communication languages, natural languages)
belong usually to classes between the Chomsky types 1 and 2. All Chomsky classes
,
m
>
