Syntax: Structural Descriptions of Sentences

Two Representations of Syntactic Structure

• Phrase structure: illustrates the constituents and its type.
• Dependency structure: Relations between words without intervening structure.

• reads

• boy

• book

• the

• a

• boy

• the

• reads

• book

• a

• DetP

• NP

• NP

• DetP

• S

• Adv

• slowly

• slowly

• adj

• arg0

• arg1

• fw

• fw

Context Free-Grammars

• String Rewriting Systems
• Transform one string to another (until termination)
• G=(V,T,P,S)
• where V: vocabulary of non-terminals
• T: vocabulary of terminals
• S: start symbol
• P: set of productions of the form
•   where   V and   (V U T)*
• Derivation: Rewrite a non-terminal with the production of the grammar until no non-terminals exist in the string.
• Start with “S”
• Sample Context-Free Grammar, derivation and derived structure.

Two Representations

• String rewriting system: we derive a string (=derived structure)
• But derivation history represented by phrase-structure tree (=derivation structure)!
• Grammar Equivalence
• Can have different grammars that generate same set of strings (weak equivalence)
• Can have different grammars that have same set of derivation trees (strong equivalence)
• Strong equivalence implies weak equivalence
• CFG Normal Forms:
• Chomsky Normal Form (   )
• Griebarch Normal Form (  w )
• Convert a grammar into CNF and GNF