Information Technology Reference
In-Depth Information
b) Every regular language has a proper subset that is also a regular language
c)
If
L
is regular, then so is
{
xy
|
x
∈
L
and
y
∈
L
}
L
and
w
R
If
L
is a regular language, then so is
{
w
:
w
∈
∈
L
}
d)
w
=
w
R
{
w
|
}
e)
is regular
STATE MINIMIZATION
4.26 Find a minimal-state FSM equivalent to that shown in Fig.
4.33
.
4.27 Show that the languages recognized by
M
and
M
≡
≡
is the equiv-
alence relation on
M
defined by states that are indistinguishable by input strings of any
length.
4.28 Show that the equivalence relation
R
L
is right-invariant.
4.29 Show that the equivalence relation
R
M
is right-invariant.
4.30 Show that the right-invariance equivalence relation (defined in Definition
4.7.2
)forthe
language
L
=
are the same, where
a
n
b
n
has an unbounded number of equivalence classes.
4.31 Show that the DFSM in Fig.
4.20
is the machine
M
L
associated with the language
L
=(
10
∗
1
+
0
)
∗
.
{
|
n
≥
0
}
PUSHDOWN AUTOMATA
4.32 Construct a pushdown automaton that accepts the following language:
L
=
{
w
|
w
is
a string over the alphabet
Σ=
{
(
,
)
}
}
.
4.33 Construct a pushdown automaton that accepts the following language:
L
=
of balanced parentheses
{
w
|
w
}
contains more 1's than 0's
.
0
0
Start
q
0
q
1
0
1
1
1
q
2
q
3
0
Figure 4.33
A four-state finite-state machine.
Search WWH ::
Custom Search