Set QG for Grammar G 1/2
24/42
Definition: Let G = (N, T, P, S) be CFG.
QG = {<y>: A ® y·z is an item in G}
Example:
Gist: QG is the set of all prefixes of the right-hand sides of rules from G.
G’expr1 = (N, T, P, E’), where N = {E’, E, F, T}, T = {i, +, *, (, )},
P = {   0: E’ ® E, 1: E ® E+T, 2: E ® T,    3: T ® T*F,
  4: T ® F, 5: F ® (E), 6: F ® i        }
Task: QG’expr1
1) Members of QG’expr1 of length 0: <e> Î QG’expr1
2) Members of QG’expr1 of length 1:
E’ ® E, E ® E+T, E ® T, T ® T*F, T ® F, F ® (E), F ® i
<E> Î QG’expr1
<T> Î QG’expr1
<F>, <(>, <i> Î QG’expr1