Chapter 4, Problem 2PS

Program Plan Intro

Pairwise Disjointness Test:

Perform the pairwise disjointness test on the following grammar rules, for each pair of rules find the disjoint such as $\text{A}\to a_i$ and $\text{A}\to a_j$.

If the intersection of $\text{First}\left(a_i\right)$ and $\text{First}\left(a_j\right)$ is equivalent to the $\varnothing$, it means pair pass the disjointness test.

Explanation of Solution

b) $\text{A}\to \text{B}\left\{\text{aB}\right\}\text{|a}$

Consider the above grammar to perform pairwise disjointness.

Find the First set for Right Hand Side of non-terminal symbol A.

FIRST (b{aB}) = {b}

FIRST (a) = {a}

Now, perform the intersection of $\text{FIRST }\left(\text{b{aB}}\right)\cap \text{FIRST\&\#}$

Explanation of Solution

c) $\text{B}\to \text{aB}\text{|}\text{a}$

Find the First set for Right Hand Side of non-terminal symbol B.

FIRST (aB) = {a}

FIRST (a) = {a}

Now, perform the intersection of $\text{FIRST }\left(\text{aB}\right)\cap \text{FIRST </}$