HW 2 Computer Science

HW-2

Computer Science

Theory of Computing (Csc 520 Course)

1.(12.5points). 

Construct a chart parse using CFG G, given below, for this ambiguous sentence:

refuse discount hardship

0  1  2 3

Note that in G, an S can simply be a VP, as in the imperative English sentences look before you leap or live for today. 

For full credit, your chart parse should capture all three of these

Meanings:

• As a VP that is a complete S, refuse discount hardship could mean do not stint on the suffering.

• refuse as an N could mean unwanted people, as in the Emma Lazarus Statue of Liberty poem:

…Give me your tired, your poor,

Your huddled masses yearning to breathe free,

The wretched refuse of your teeming shore. …

With that sense of refuse, refuse discount hardship could mean that those whom Liberty gathers downplay their difficulties.

• refuse as a noun could also mean objects people throw away. So, as an NP, not in itself an S,

refuse discount hardship could mean something like a difficulty caused by a lack of coupons

at thrift stores.

Include all entries, even if they are not continued on subsequent rows, as well as all complete

parses for S that do not consume the entire input string.

G = {

S → NP VP | VP

NP → N | AttrNP

AttrNP → NP N

VP → V | VP NP

N → discounts | hardship | refuse

V → discount | refuse |

}

Remember that—

AttrNP stands for attribute noun phrase, where one noun modifies another