A linear CFG is a CFG where all productions have the forms A → wBx or A → w (where A,B V and w, x *). Show that ever
Posted: Sat May 14, 2022 4:55 pm
A linear CFG is
a CFG where all productions have the forms A →
wBx or A → w (where A,B V and
w, x *).
Show that every linear CFG can be converted to a CFG in
Linear Normal Form where all productions
have the following forms:
A → aB,
A → Ba, or A → a (where A, B V ,
and a U
{}).
a CFG where all productions have the forms A →
wBx or A → w (where A,B V and
w, x *).
Show that every linear CFG can be converted to a CFG in
Linear Normal Form where all productions
have the following forms:
A → aB,
A → Ba, or A → a (where A, B V ,
and a U
{}).