CSC 9010 Natural Language Processing Lecture 6 Context Free Grammars Paula Matuszek Mary Angela Papalaskari Presentation slides adapted from Martin http www cs colorado edu martin csci5832 html McCoy http www cis udel edu mccoy courses cisc882 03f after Owen Rambow 01 14 19 CSC 9010 NLP Context Free G rammars 1 Grammaticality Does NOT depend on Having heard the sentence before The sentence being true Julia Roberts wears green pyjamas The sentence being meaningful Colorless green ideas sleep furiously Furiously sleep ideas green colorless My groklar is sklivier than your bosser Grammatically is a formal property that we can investigate and describe 01 14 19 CSC 9010 NLP Context Free G rammars 2 Syntax Words are strung together to form components of sentences which are in turn strung together to form other components or sentences New Concept Constituency Constituent group of words that behave as a single unit E g noun phrase NP 01 14 19 CSC 9010 NLP Context Free G rammars 3 Evidence Whole group appears in similar syntactic environment eg before a verb Preposed postposed constructions Note notions of meaning play no role in syntax sort of 01 14 19 CSC 9010 NLP Context Free G rammars 4 What is Syntax Study of structure of language Goal relate surface form to semantics Morphology phonology semantics farmed out mainly issue is word order and structure Representational device is tree structure 01 14 19 CSC 9010 NLP Context Free G rammars 5 What About Chomsky At birth of formal language theory comp sci and formal linguistics Major contribution syntax is cognitive reality Humans able to learn languages quickly but not all languages universal grammar is biological Goal of syntactic study find universal principles and language specific parameters Specific Chomskyan theories change regularly These ideas adopted by almost all contemporary syntactic theories principles and parameters type theories 01 14 19 CSC 9010 NLP Context Free G rammars 6 Types of Linguistics Descriptive account of syntax of a language often good enough for NLP engineering work Explanatory principles and parameters style account of syntax of preferably several languages Prescriptive prescriptive linguistics not very useful in any way We don t need no education 01 14 19 CSC 9010 NLP Context Free G rammars 7 Syntax Why should you care Grammar checkers Question answering Information extraction Machine translation 01 14 19 CSC 9010 NLP Context Free G rammars 8 Context Free Grammar Example S NP VP NP Det NOMINAL NOMINAL Noun VP Verb Det a Noun flight Verb left 01 14 19 CSC 9010 NLP Context Free G rammars Productions 9 Earlier examples S A A b a a A a A S NP VP NP PrNoun NP Det Noun Det a the Noun cat dog book PrNoun samantha elmer fido VP IVerb TVerb NP IVerb ran slept ate TVerb hit kissed ate Regular language Regular 01 14 19 CSC 9010 NLP Context Free G rammars 10 CFGs S NP VP This says that there are units called S NP and VP in this language That an S consists of an NP followed immediately by a VP Doesn t say that that s the only kind of S Nor does it say that this is the only place that NPs and VPs occur 01 14 19 CSC 9010 NLP Context Free G rammars 11 Generativity As with FSAs and FSTs you can view these rules as either analysis or synthesis machines Generate strings in the language Reject strings not in the language Impose structures trees on strings in the language 01 14 19 CSC 9010 NLP Context Free G rammars 12 Derivations A derivation is a sequence of rules applied to a string that accounts for that string Covers all the elements in the string Covers only the elements in the string 01 14 19 CSC 9010 NLP Context Free G rammars 13 Context Free Grammars Defined in formal language theory comp sci Terminals nonterminals start symbol rules String rewriting system Start with start symbol rewrite using rules done when only terminals left NOT A LINGUISTIC THEORY just a formal device 01 14 19 CSC 9010 NLP Context Free G rammars 14 Derivations as Trees Phrase structure tree 01 14 19 CSC 9010 NLP Context Free G rammars 15 Another example Types of Nodes the Det boy N likes V a Det girl N S nonterminal symbols constituents NP DetP the 01 14 19 NP likes boy DetP a girl terminal symbols words CSC 9010 NLP Context Free G rammars 16 CFG Example Many possible CFGs for English here is an example fragment S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the the very small boy likes 01 14 19 CSC 9010NLP Context Free G a girl rammars 17 Derivations in a CFG S S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S CSC 9010 NLP Context Free G rammars 18 Derivations in a CFG NP VP S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP CSC 9010 NLP Context Free G rammars VP 19 Derivations in a CFG DetP N VP S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP DetP VP N CSC 9010 NLP Context Free G rammars 20 Derivations in a CFG the boy VP S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP DetP VP N the boy CSC 9010 NLP Context Free G rammars 21 Derivations in a CFG the boy likes NP S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP DetP VP N V NP the boy likes CSC 9010 NLP Context Free G rammars 22 Derivations in a CFG the boy likes a girl S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP DetP VP N V NP the boy likes DetP CSC 9010 NLP Context Free G rammars a N girl 23 Derivations in a CFG Order of Derivation Irrelevant NP likes DetP girl S NP VP VP V NP NP DetP N AdjP NP AdjP Adj Adv AdjP N boy girl V sees likes Adj big small Adv very DetP a the 01 14 19 S NP VP V NP likes DetP CSC 9010 NLP Context Free G rammars N girl 24 Derivations of CFGs String rewriting system we derive a …