Question

Perform the pairwise disjointness test for each of the following grammar rules.

1. → aBc | bB | Bbc
2. → aBc | bA | aBbc
3. → aaAc | b | caBc

Answer 1

pairwise disjointness test is performed by finding the first of the RHS of each rule.

first is determined by finding the first non terminal.If the intersection of the firsts of any grammer is not null, then the grammar fails the test. else passes the test.

A -->aBc| bB | Bbc

first(aBc) = {a}

first(bB) = {b}

first(Bbc) = {a,b}

The grammar fails since there are intersecting non terminals(a and b).

B -->aBc | bA | aBbc

first(aBc) = {a}

firs(bA) = {b}

first(aBbc) ={a}

Grammar fails the test since there is a common non terminal {a}

C -->aaAc | b | caBc

first(aaAc) = a

first(b) = b

first(caBc)= c

grammar passes the test since the intersection is null