Information Technology Reference
In-Depth Information
EXAMPLE
4.9.1
Consider the grammar
G
1
=(
N
1
,
T
1
,
R
1
,
S
)
,where
N
1
=
{
S
,
B
,
C
}
,
T
1
=
{
a
,
b
,
c
}
R
and
1
consists of the following rules:
a
)
→
a
SBC
d
)
a
B
→
ab
g
)
c
C
→
cc
S
b
)
→
a
BC
e
)
b
B
→
bb
S
c
)
CB
→
f
)
b
C
→
bc
BC
⇒
aa
BBCC
. One application of (d), one of (e), one of (f ), and one of (g) reduces it to the string
aabbcc
. Since one application of (a) and one of (b) produces the string
aa
BBCC
, it follows
that the language
L
(
G
1
)
contains
aabbcc
.
Similarly, two applications of (a) and one of (b) produce
aaa
BCBCBC
, after which three
applications of (c) produce the string
aaa
BBBCCC
. One application of (d) and two of (e)
produce
aaabbb
CCC
, after which one application of (f ) and two of (g) produces
aaabbbccc
.
In general, one can show that
L
(
G
1
)=
Clearly the string
aa
BCBC
can be rewritten as
aa
BBCC
using rule (c), that is,
aa
BCBC
{
a
n
b
n
c
n
|
n
≥
}
1
. (See Problem
4.38
.)
4.9.2 Context-Sensitive Languages
The context-sensitive languages are exactly the languages accepted by linear bounded automata,
nondeterministic Turing machines whose tape heads visit a number of cells that is a constant
multiple of the length of an input string. (See Problem
4.36
.)
DEFINITION
4.9.2
A
context-sensitive grammar
G
is a phrase structure grammar
G
=(
N
,
T
R
,
S
)
in which each rule
(
a
,
b
)
∈R
satisfies the condition that
b
has no fewer characters
,
than does
a
,namely,
|
a
|≤|
b
|
. The languages defined by context-sensitive grammars are called
context-sensitive languages
(CSL).
Each rule of a context-sensitive grammar maps a string to one that is no shorter. Since the
left-hand side of a rule may have more than one character, it may make replacements based
on the context in which a non-terminal is found. Examples of context-sensitive languages are
giveninProblems
4.38
and
4.39
.
4.9.3 Context-Free Languages
As shown in Section
4.12
, the context-free languages are exactly the languages accepted by
pushdown automata.
DEFINITION
4.9.3
A
context-free grammar
G
=(
N
,
T
,
R
,
S
)
is a phrase structure grammar
in which each rule in
V
∗
has a single non-terminal on the left-hand side. The languages
defined by context-free grammars are called
context-free languages
(CFL).
R⊆N×
Each rule of a context-free grammar maps a non-terminal to a string over
V
∗
without
regard to the context in which the non-terminal is found because the left-hand side of each
rule consists of a single non-terminal.
EXAMPLE
4.9.2
Let
N
2
=
{
S
,
A
}
,
T
2
=
{
,
a
,
b}
,and
R
2
=
{
S
→ a
S
b
,
S
→ }
. Then the
grammar
G
2
=(
a
n
b
n
N
2
,
T
2
,
R
2
,
S
)
is context-free and generates the language
L
(
G
2
)=
{
|
n
≥
a
S
b
be applied
k
times to produce the string
a
k
S
b
k
.Afinal
application of the last rule establishes the result.
0
}
. To see this, let the rule
S
→
Search WWH ::
Custom Search