TA: Jade Cheng (TA)
ICS 313
HW 9 Homework on auxiliary algorithms
Due 2/17/19
[Problem 1]
Consider the grammar:
S --> XY
H --> XY | R
Z --> N
X --> YY
Y --> NZZ | R
R --> epsilon
1. Which symbols are reachable from the goal symbol?
S x
X x
Y x
H
R x
Z x
N x
Answer: S, X, Y, R, Z, N are reachable from the goal symbol.
2. From which symbols is it possible to derive a terminal string?
S x
X x
Y x
H x
R
Z x
N x
Answer: from S, X, Y, H, Z, N it is possible to derive a terminal string.
3. Which symbols are vanish?
S x
X x
Y x
H x
R x
Z
N
Answer: S, X, Y, H, R are vanish.
[Problem 2]
Consider the grammar:
S --> U | n
U --> R
X --> d | e
Y --> RV
R --> XX | ab
Z --> Ze
T --> f
Evaluate the set heads (UXYZn)
The possible set of heads are:
S
U x
n
R x
X x
d x
e x
Y
V
a x
b
Z
T
f
Answer: U, R, X, d, e, a are in the set of heads.
