Greibach Normal Form (GNF)
Definition:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG.
G
is in
Greibach
normal form
if
every
rule in
P
is of
this form
•
A
®
a
x
, where
A
Î
N
,
a
Î
T
,
x
Î
N
*
Example:
G
= (
N
,
T
,
P
,
S
), where
N
= {
B
,
S
},
T
= {
a
,
b
},
P
= {
S
®
a
SB
,
S
®
a
B
,
B
®
b
}
is in Greibach normal form.
Note:
L
(
G
)
= {
a
n
b
n
:
n
³
1}
3
/31