Theory of computing problem

Making it CNF prep G for CYK parsing or analysis [15 pts]

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

We will start with

1. S -> a A B b

2. S -> e E

3. A -> C C

4. C -> epsilon

5. C -> x

6. B -> d d

7. 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]

o Which rules derive string?

o Which rules do not derive strings and should be removed?

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

o Which rules are reachable from S?

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

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

1. S -> a A B b

2. A -> C C

3. C -> epsilon

4. C -> x

5. 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]

1. S -> a A B b

2. S -> a B b

3. A -> C C

4. A -> C

5. C -> x

6. 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]

1. S -> a A B b

2. S -> a B b

3. A -> C C

4. A -> x

5. C -> x

6. B -> d d

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

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

2. Stratify mixed rules. [1]

Change this mixed rule:

To what????

Change this mixed rule:

To what???

Change B -> d d to what???

3. 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