Information Technology Reference
In-Depth Information
REGULAR LANGUAGES
4.44 Show that the regular language
G
4
described in Example
4.9.4
is
L
(
G
4
)=(
01
)
∗
0.
4.45 Show that grammar
G
=(
N
,
T
,
R
,
S
)
,where
N
=
{
A
,
B
,
S
}
,
T
=
{
a
,
b
}
and the
R
rules
are given below, is regular.
a
)
→
ab
A
d
)
→
f
)
→
a
S
S
S
B
b
)
→
ba
B
e
)
→
b
S
g
)
→
b
S
A
A
c
)
→
S
B
Give a derivation for the string
abbbaa
.
4.46 Provide a regular grammar generating strings over
{
}
not containing 00.
4.47 Give a regular grammar for each of the following languages and show that there is a
FSM that accepts it. In all cases
Σ=
0, 1
{
}
0, 1
.
L
=
{
w
|
the length of
w
is odd
}
a)
L
=
{
w
|
w
contains at least three 1s
}
b)
REGULAR LANGUAGE RECOGNITION
4.48 Construct a finite-state machine that recognizes the language generated by the grammar
G
=(
N
T
R
,
S
)
,where
N
{
}
T
=
{
x
,
y
}
R
,
,
=
S
,
X
,
Y
,
,and
contains the following
.
4.49 Describe finite-state machines that recognize the following languages:
a)
→
x
X
,
S
→
y
Y
,
X
→
y
Y
,
Y
→
x
X
,
X
→
,and
Y
→
rules:
S
}
∗
|
{
w
∈{
a
,
b
w
has an odd number of
a
's
}
}
∗
|
}
4.50 Show that, if
L
is a regular language, then the language obtained by reversing the letters
in each string in
L
is also regular.
4.51 Show that, if
L
is a regular language, then the language consisting of strings in
L
whose
reversals are also in
L
is regular.
{
w
∈{
a
,
b
w
has
ab
and
ba
as substrings
b)
PARSING CONTEXT-FREE LANGUAGES
4.52 Use the algorithm of Theorem
4.11.2
to construct a parse tree for the string
(
a
∗
b
+
(
a
+
b
)
generated by the grammar
G
5
of Example
4.11.2
, and give a leftmost and
a rightmost derivation for the string.
4.53 Let
G
=(
a
)
∗
N
T
R
,
S
)
be the context-free grammar with
N
=
S
and
T
=
{
(
,
)
,0
}
,
,
R
=
{
→
→
→
(
S
)
}
with rules
0,
S
SS
,
S
. Use the algorithm of Theorem
4.11.2
to
S
generate a parse tree for the string
(
0
)((
0
))
.
CFL ACCEPTANCE WITH PUSHDOWN AUTOMATA
4.54 Construct PDAs that accept each of the following languages:
a)
a
n
b
n
{
|
n
≥
}
0
ww
R
}
∗
}
{
|
w
∈{
a
,
b
b)
}
∗
,
w
=
w
R
{
w
|
w
∈{
a
,
b
}
c)
Search WWH ::
Custom Search