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.