Information Technology Reference
In-Depth Information
The
language recognized
by an FSM is defined in two ways. It is the set of input strings
that cause the FSM to produce a particular letter as its last output or to enter one of the set
of final states on its last input. Thus, the FSM of Fig.
1.8
recognizes the set of binary strings
containing an odd number of 1's. It also recognizes the set of binary strings containing an even
number of 1's because they result in a last output of 0.
An FSM can also
compute a function
. The most general function that it computes in
T
stepsisthefunction
f
(
T
)
M
Ψ
T
that maps the initial state
s
and the
T
inputs
w
1
,
w
2
,
...
,
w
T
to the
T
outputs
y
1
,
y
2
,
...
,
y
T
. It can also compute any other
function obtained by ignoring some outputs or fixing either the initial state or some inputs
or both.
The class of languages recognized by finite-state machines (the
regular languages
)isnot
rich enough to describe easily the important programming languages that are in use today. As
a consequence, other languages, such as the context-free languages, are employed.
Context-
free languages
(which include the regular languages) require computers with potentially un-
bounded storage for their recognition. The class of computers that recognizes exactly the
context-free languages are the nondeterministic pushdown automata, pushdown automata in
which the control unit is nondeterministic; that is, some of its states can have multiple poten-
tial successor states.
The strings in regular and context-free languages (and other languages as well) can be
generated by grammars. A context-free grammar
G
=(
Σ
T
:
Q
×
→
Q
×
N
,
T
,
R
,
S
)
consists of sets of
terminal
and
non-terminal symbols
,
by which each non-terminal
is replaced with one or more strings of terminals and non-terminals. All string generations
start with the special
start
non-terminal
S
. The language generated by
G
,
L
(
G
)
,containsthe
strings of terminal characters produced by rewriting strings in this fashion. This is illustrated
by the context-free grammar
G
with two rules shown below.
T
and
N
respectively, and rules
R
EXAMPLE
1.4.1
G
=(
N
,
T
,
R
,
S
)
,where
N
=
{
S
}
,
T
=
{a
,
b}
,and
R
consists of the two
rules
(
a
)
→
a
S
b
(
b
)
→
ab
S
S
Each application of a rule derives another string, as shown below. This grammar has only
two derivations, namely
S
→
→
ab. The second derivation is always the last to be
used. (Recall that the language
L
(
G
)
contains only terminal strings.)
a
S
band
S
→
a
S
b
S
→
aa
S
bb
→
aaa
S
bbb
→
aaaabbbb
As can be seen by inspection, the only strings in
L
(
G
)
are of the form
a
k
b
k
,where
a
k
denotes
the letter
a
repeated
k
times. Thus,
L
(
G
)=
a
k
b
k
.
Once a grammar for a regular or context-free language is known, it is possible to
parse
a
string in the language. In the above example this amounts to determining the number of times
that the first rule is applied.
To develop some intuition for the use of the pushdown automaton as a recognizer for
context-free languages, observe that we can determine the number of applications of the first
rule in this language by pushing each instance of
a
onto a stack and then popping
a
's a s
b
's a re
{
|
k
≥
1
}
Search WWH ::
Custom Search