1. (12.5 points) Construct a chart parse for the ambiguous sentence:

smoke signals lit fires

0 1 2 3 4

The sentence has at least two possible meanings: 1. fires were caused by smoke

signals; and 2. smoke indicates the presence of fire. Complete a chart parse

showing both meanings.

G {

S NP VP

NP N | Prcp N | AttrNP

AttrNP NP N

VP V | V NP

N smoke | signals | fires

V signals| lit

Prcp lit

}

Prcp represents a participle, a word whose function is part adjective and part verb.

For example, the present participle of the verb to fail is failing, as in failing

infrastructure.

AttrNP represents an attributive noun phrase, in which a noun phrase modifies a

noun, For example, wool socks, and liquor store.

2. (12.5 points = {a,b}, L = {s : |s| is even and #a(1st half of s) = #a(2nd half

of s) + 1}. For example, ababba L; ababa L (odd length); and ababaa L

(same number of a's in both halves of string).