Information Technology Reference
In-Depth Information
PHRASE STRUCTURE LANGUAGES
4.34 Give phrase-structure grammars for the following languages:
a)
}
∗
}
{
ww
|
w
∈{
a
,
b
0
2
i
b)
{
|
i
≥
1
}
4.35 Show that the following language can be described by a phrase-structure grammar:
a
i
{
|
i
is not prime
}
CONTEXT-SENSITIVE LANGUAGES
4.36 Show that every context-sensitive language can be accepted by a
linear bounded au-
tomaton
(LBA), a nondeterministic Turing machine in which the tape head visits a
number of cells that is a constant multiple of the number of characters in the input
string
w
.
Hint:
Consider a construction similar to that used in the proof of Theorem
5.4.2
.
Instead of using a second tape, use a second track on the tape of the TM.
4.37 Show that every language accepted by a linear bounded automaton can be generated by
a context-sensitive language.
Hint:
Consider a construction similar to that used in the proof of Theorem
5.4.1
but
instead of deleting characters at the end of TM configuration, encode the end markers
[
and
]
by enlarging the tape alphabet of the LBA to permit the first and last characters
to be either marked or unmarked.
4.38 Show that the grammar
G
1
in Example
4.9.1
is context-sensitive and generates the
language
L
(
G
1
)=
a
n
b
n
c
n
{
|
n
≥
}
1
.
0
2
i
{
|
i
≥
}
4.39 Show that the language
is context-sensitive.
4.40 Show that the context-sensitive languages are closed under union, intersection, and
concatenation.
1
CONTEXT-FREE LANGUAGES
4.41 Show that language generated by the context-free grammar
G
3
of Example
4.9.3
is
L
(
G
3
)=
{
ca
n
ca
n
cb
m
cb
m
c
|
n
,
m
≥
}
.
4.42 Construct context-free grammars for each of the following languages:
a)
0
ww
R
}
∗
}
{
|
w
∈{
a
,
b
}
∗
,
w
=
w
R
{
w
|
w
∈{
a
,
b
}
b)
L
=
{
w
|
w
hastwiceasmany0'sas1's
}
c)
4.43 Give a context-free grammars for each of the following languages:
a)
}
∗
|
{
w
∈{
a
,
b
w
has twice as many
a
's a s
b
's
}
a
r
b
s
{
|
r
≤
s
≤
2
r
}
b)
Search WWH ::
Custom Search