Information Technology Reference
In-Depth Information
THEOREM
4.10.1
The languages
L
(
G
)
and
L
(
G
)
∪{}
generated by regular grammars
G
and
recognized by finite-state machines are the same.
Proof
Given a regular grammar
G
, we construct a corresponding NFSM
M
that accepts
exactly the strings generated by
G
. Similarly, given a DFSM
M
we construct a regular
grammar
G
that generates the strings recognized by
M
.
From a regular grammar
G
=(
N
T
R
,
S
)
with rules
R
→
a
and
,
,
of the form
A
b
C
we create a grammar
G
generating the same language by replacing a rule
A
→
→
a
A
→
a
B
and
B
→
where
B
is a new non-terminal unique to
A
→
a
.Thus,
with rules
A
every derivation
S
∗
∈T
∗
, now corresponds to a derivation
S
∗
⇒
G
w
,
w
⇒
G
w
Bwhere
. Hence, the strings generated by
G
and
G
are the same.
Now construct an NFSM
M
G
whose states correspond to the non-terminals of this new
regular grammar and whose input alphabet is its set of terminals. Let the start state of
M
G
be labeled
S
. Let there be a transition from state
A
to state
B
on input
a
if there is a rule
A
→
B
in
G
.
Clearly, every derivation of a string
w
in
L
(
G
)
corresponds to a path in
M
that begins in
the start state and ends on a final state. Hence,
w
is accepted by
M
G
. On the other hand,
if a string
w
is accepted by
M
G
, given the one-to-one correspondence between edges and
rules, there is a derivation of
w
from
S
in
G
. Thus, the strings generated by
G
and the
strings accepted by
M
G
are the same.
Now assume we are given a DFSM
M
that accepts a language
L
M
. Create a grammar
G
M
whose non-terminals are the states of
M
and whose start symbol is the start state of
M
.
G
M
has a rule of the form
q
1
→
→
a
B
in
G
. Let a state
B
be a final state if there is a rule of the form
B
→
aq
2
if
M
makes a transition from state
q
1
to
q
2
on input
a
. If state
q
is a final state of
M
, add the rule
q
. If a string is accepted by
M
,thatis,it
causes
M
to move to a final state, then
G
M
generates the same string. Since
G
M
generates
onlystringsofthiskind,thelanguageacceptedby
M
is is
L
(
G
M
)
.Nowconvert
G
M
to
a regular grammar
G
M
by replacing each pair of rules
q
1
→
→
aq
2
,
q
2
→
by the pair
q
1
→
aq
2
,
q
1
→
a
, deleting all rules
q
→
corresponding to unreachable final states
q
,
=
L
(
G
M
)
.
and deleting the rule
S
→
if
∈
L
M
.Then,
L
M
−{
}
=
L
(
G
M
)
−{
}
A
0
0
Start
1
S
B
0
0
C
D
Figure 4.27
A nondeterministic FSM that accepts a language generated by a regular language in
which all rules are of the form
A
→
. A state is associated with each non-terminal, the
start symbol
S
is associated with the start state, and final states are associated with non-terminals
A
such that
A
→ b
C
or
A
→
. This particular NFSM accepts the language
L
(
G
4
)
of Example
4.9.4
.
Search WWH ::
Custom Search