Information Technology Reference
In-Depth Information
where
A
is the
alphabet
,
Q
the set of
states
,
F
the set of
final states
,
q
0
is the
initial
state
,and
τ
is the
state transition
function, from pairs of symbols and states to states:
τ
:
A
×
Q
→
Q
.
M reads
an input string
and in
the state
q
0
as current state. The automaton
M
applies the transition function
α
, starting from the first symbol (from the left) of
α
τ
to
the symbol
x
that it reads and to its current state
q
,bytaking
as next current
state, and by passing to read the symbol on the right of the symbol
x
previously read.
When the whole input string is read, then
M
halts. If the state of
M
, when it halts,
belongs to
F
,then
τ
(
x
,
q
)
α
is accepted by
M
,otherwise
α
is not accepted by
M
.
We can express the transition function of an automaton by a rewriting relation. For
example the transition of the automaton given in Fig. 6.2 could be given by (
q
0
initial state and
q
0
,
q
1
final states):
Ta b l e 6 . 9
The automaton recognizing the bipartite language expressed by state transition
rules
q
0
a
→
q
0
q
0
b
→
q
1
q
1
b
→
q
1
q
1
a
→
q
2
q
2
a
→
q
2
q
2
b
→
q
2
In terms of rewriting relation, the language recognized by a finite automaton
M
can be defined in the following way:
A
∗
|
q
0
α
→
∗
M
q
f
,
L(
M
)=
{
α
∈
q
f
∈
F
}.
The transition rules representation of a finite state automaton can be easily trans-
formed into a grammar if we start from the initial state
q
0
and in passing from a
state to another one we generate a symbol instead of reading it. For example, in Ta-
ble 6.10, the rules of automaton of Table 6.9 are transformed into generative rules
R
which provide the type 3 grammar
G
generating
the bi-partite language. In this case, the initial state of the automaton becomes the
start symbol of the grammar
G
,andrules
q
0
→
=(
{
a
,
b
,
q
0
,
q
1
,
q
2
},{
a
,
b
},
q
0
,
R
)
a
,
q
0
→
b
,and
q
1
→
b
are added for
deleting the final states
q
0
,
q
1
. Transition rules of the automaton which are relative to
state
q
2
do not need to be translated into generative rules. This method can be easily
generalized, by proving that any language recognized by a finite automaton is also
