Making it CNF prep G for CYK parsing or analysis

--------------------------------------------------------------------------------------------

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.

You may refer to the rule numbers in answering which rules questions!

a) Remove all useless rules. [2pts]

1- Start bottom up from terminal strings.[1]

Which rules derive string?

Which rules do not derive strings and should be removed?

2- Then start top down from S.[1]

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) [1] ?

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

3- List all the ways to make such non-terminals disappear from the right side [1].

Newly added rules are:

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

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. =*=> )[1]:

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

List added rules:

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

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

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) [1]

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

Stratify mixed rules. [1]

Change this mixed rule:

To what?

Change this mixed rule:

To what?

Change B -> d d to what?

List the resulting grammar: [1]

(should have only one terminal or only 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