Definition: Let G = (N, T, P, S) be a CFG. The language
generated by G, L(G), is defined as
L(G) = {w: w Î T*, S Þ* w}
Generated Language
G =
(N, T, P, S), let w =
a1a2…an; ai Î T for i = 1..n
S Þ … Þ … Þ a1a2…an
w
G generates a terminal string w by a sequence
of derivation steps from S
to w
Gist:
then w Î L(G);
otherwise, w Ï L(G)
Illustration:
8/50