Information Technology Reference
In-Depth Information
a
)
→
d
)
→
b
B
c
S
AB
B
b
)
→
a
A
e
)
→
A
B
c
)
→
A
Thus, the languages
L
1
and
L
2
are context-free. However, their intersection is
L
1
∩
L
2
=
a
n
b
n
c
n
{
, which was shown in Lemma
4.13.2
not to be context-free. Thus, the set
of CFLs is not closed under intersection, nor is it closed under complementation.
|
n
≥
0
}
.......................................
Problems
FSM MODELS
4.1 Let
M
=(Σ
,
Ψ
,
Q
,
δ
,
λ
,
s
,
F
)
be the FSM model described in Definition
3.1.1
.It
differs from the FSM model of Section
4.1
in that its output alphabet
Ψ
has been
explicitly identified. Let this machine recognize the language
L
(
M
)
consisting of input
strings
w
that cause the last output produced by
M
to be the first letter in
Ψ
.Show
that every language recognized under this definition is a language recognized according
to the “final-state definition” in Definition
4.1.1
and vice versa.
4.2 The
Mealy machine
is a seven-tuple
M
=(Σ
,
Ψ
,
Q
,
δ
,
λ
,
s
,
F
)
identical in its def-
inition with the Moore machine of Definition
3.1.1
except that its output function
λ
:
Q
×
→
Ψ
depends on both the current state and input letter, whereas the output
function
λ
:
Q
Σ
Ψ
of the Moore FSM depends only on the current state. Show that
the two machines recognize the same languages and compute the same functions with
the exception of
.
4.3 Suppose that an FSM is allowed to make state
-transitions, that is, state transitions
on the empty string. Show that the new machine model is no more powerful than the
Moore machine model.
Hint:
Show how
-transitions can be removed, perhaps by making the resultant FSM
nondeterministic.
→
EQUIVALENCE OF DFSMS AND NFSMS
4.4 Functions computed by FSMs are described in Definition
3.1.1
. Can a consistent
definition of function computation by NFSMs be given? If not, why not?
4.5 Construct a deterministic FSM equivalent to the nondeterministic FSM shown in
Fig.
4.32
.
REGULAR EXPRESSIONS
4.6 Show that the regular expression 0
(
0
∗
10
∗
)
+
defines strings starting with 0 and con-
taining at least one 1.
4.7 Show that the regular expressions 0
∗
,0
(
0
∗
10
∗
)
+
,and1
(
0
+
1
)
∗
partition the set of all
strings over 0 and 1.
4.8 Give regular expressions generating the following languages over
Σ=
{
0, 1
}
:
Search WWH ::
Custom Search