We will start with

S -> a A B b

S -> e E

A -> C C

C -> epsilon

C -> x

B -> d d

F -> f

Follow the following instructions step by step and answer each question.

a) Remove all useless rules. [2pts]

1- Start bottom up from terminal strings.

Which rules derive string?

Which rules do not derive strings and should be removed?

2- Then start top down from S.

Which rules are reachable from S?

Which rules are not reachable from S and should be removed?

b) Make it epsilon-free. [4pts]

S -> a A B b

A -> C C

C -> epsilon

C -> x

B -> d d

1- Which non-terminals go directly or indirectly to epsilon (?? =*=> epsilon)?

2- Which rules use such non-terminals on the right side?

3- List all the ways to make such non-terminals disappear from the right side

Newly added rules are:

4- What epsilon-rules will now be removed (they go directly to epsilon)?

c) Make it chain-free (no ->). [4pts]

S -> a A B b

S -> a B b

A -> C C

A -> C

C -> x

B -> d d

1- List all chain derivations (i.e. =*=> ):

2- For each chain, add rule(s) to skip the right side non-terminal.

List added rules:

3- Delete all chain rules. List the ones to delete:

4- Did any rule become useless and need to be removed? Which ones?

d) Make it stratified (no non-terminal terminal mixture).[3pts]

S -> a A B b

S -> a B b

A -> C C

A -> x

C -> x

B -> d d

Add N#-> rule for each terminal (a,b,d,x)

(i.e. use N1, N2, etc.):

Stratify mixed rules.

Change this mixed rule:

To what?

Change this mixed rule:

To what?

Change B -> d d to what?

List the resulting grammar:

(should have only one terminal or non-terminals on the RHS)

e) Make the result of (d), binary (i.e. 2 non-terms) [2pts]

1- Change this rule:

To what?

Change this rule:

To what?

2- Final Result is:

All rules will be of the form N -> N N or N -> t