Fill in the ellipses and question marks to complete the chart parse using CFG G, for this ambiguous sentence

CSC 520 Spring 2020 HW #2

1. (12.5points). Fill in the ellipses and question marks to complete the chart parse using CFG G, for this ambiguous sentence: DB shows spread 0 1 2 3 For full credit, your chart parse should capture three possible meanings: • As an S, DB shows spread could mean that a database shows that something is spreading.

• As an S, DB shows spread could mean that exhibitions of a database product, such as Oracle, are taking place in more locations.

• As an NP, DB shows spread could mean could mean the phenomenon of increasing exhibitions of a database product, and could be part of a sentence such as DB shows spread noted.

G = { S → NP VP NP → N | AttrNP VP → V | VP NP AttrNp → NP N N → DB | shows | spread V → shows | spread }

Remember that AttrNP stands for attribute noun phrase, where one noun modifies another, as in homework assignment or summer vacation.

row 0: ℇ 0.a S → • NP VP [0,0] anticipate S 0.b NP → • N [0,0] anticipate for 0.a 0.c NP → • AttrNP [0,0] anticipate for 0.a 0.d AttrNP → • NP N [0,0] anticipate for 0.c

row 1: DB 1.a N → DB • [0,1] scan 1.b NP → N • [0,1] apply 1.a to 0.b

… … … row 2: shows 2.a N → shows • [1,2] scan 2.b AttrNP → NP N • [0,2] apply 2.a to 1.? … … … 2.? V → shows • [1,2] scan … … … row 3: spread 3.a N → spread • [2,3] scan

… … … 3.? V → spread • [2,3 ] scan 3.? VP → V • [2,3] apply 3.? to 2.? … … …

2. (12.5 points) ∑={a,b}, L = { s: #b(s) = n!, n ≥ 1 and s does not start and end with the same symbol}. For example, ab⁶ ∈ L; t = b⁵ab ∉ L because t starts and ends with the same symbol; ab⁴ ∉ L because 4 ≠ n! for an n ≥ 1. Use the CF pumping theorem to show that ∉ CFLs. You may also use the closure property of CFLs under intersection with a regular language.