Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Making it CNF prep G for CYK parsing or analysis -------------------------------------------------------------------------------------------- We will start with S -> a A B b S -> e E

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Databases Demystified

Authors: Andrew Oppel

1st Edition

0072253649, 9780072253641

More Books

Students also viewed these Databases questions

Question

1. Traditional and modern methods of preserving food Articles ?

Answered: 1 week ago

Question

What is sociology and its nature ?

Answered: 1 week ago

Question

What is liquidation ?

Answered: 1 week ago

Question

Explain the different types of Mergers.

Answered: 1 week ago