Information Technology Reference
In-Depth Information
generated by a type 3 grammar. In an analogous way it is simple to define the inverse
process of constructing a finite automaton which recognizes the language generated
by a type 3 grammar. In conclusion, the two kinds of formal devices determine the
same class of languages.
Ta b l e 6 . 1 0
A type 3 grammar generating the bi-partite language
q
0
→
aq
0
q
0
→
bq
1
q
1
→
bq
1
q
0
→
a
q
0
→
b
q
1
→
b
A finite state automaton
M
is
deterministic
when, for every state, only one pos-
sible transition can be applied. This means that the codomain of
τ
is
Q
:
τ
:
A
×
Q
→
Q
.
A deterministic automaton
M
recognizes a string
α
(over its alphabet) when starting
in the initial state and reading
on its tape (from the first symbol on the left to the
last on the right), by applying the transition function
α
,
M
ends in a final state.
A finite state automaton
M
is
nondeterministic
when, for every state, one among
a set of possible transitions can be applied. This means that the codomain of
τ
τ
is
P(
Q
)
:
τ
:
A
×
Q
→
P(
Q
)
.
A nondeterministic automaton
M
recognizes a string
α
(over its alphabet) when
starting in the initial state and reading
on its tape, if
M
chooses at each step one
of the possible transitions, for some sequence of choices,
M
ends in a final state.
α
a
n
b
n
Proposition 6.3.
The language bi-somatic
L(
)
cannot be recognized by any fi-
nite state deterministic automaton.
Proof.
Any finite state automaton
M
determines an equivalence relation
≡
M
be-
tween the strings over the alphabet of
M
such that
α
≡
M
β
if
M
finishes reading
both the strings in the same state. Now, let
the alphabet of
M
,thenhaving
M
a finite number of states, there exist two distinct natural numbers
n
{
a
,
b
}
,
m
such that
a
n
≡
M
a
m
. If we concatenate both
a
n
and
a
m
by the same string
b
n
,thenweget
a
n
b
n
and
a
m
b
n
. Assume that
M
could recognize
, then, when
M
reads
a
n
and
a
m
,
it ends in the same state, according to the equivalence
a
n
b
n
L(
)
≡
M
, therefore, it ends in the
same state also when it reads both strings
a
n
b
n
and
a
m
b
n
. But this is a contradiction
because we assumed that
M
is able to recognize
a
n
b
n
L(
)
.
