CONTEXT-FREE GRAMMARS - University of Essex

CONTEXT-FREE GRAMMARS - University of Essex

CONTEXT-FREE GRAMMARS 1 Syntactic analysis (Parsing) S NP AT the VP NNS

VBD children ate NP AT the 2 NLE

NN cake Beyond regular languages: Context-Free Grammars S NP VP NP Det Nominal Nominal Noun VP V 4 Det the Det a

Noun flight V left NLE Derivations A DERIVATION of a string is a sequence of rule applications E.g., the string a flight can be derived from the grammar above and symbol NP by the (leftmost first) derivation

5 NP => Det Nominal => a Nominal => a Noun => a flight Derivations can be visualized as PARSE TREES The LANGUAGE defined by a CFG is the set of strings derivable from the start symbol S (for Sentence) NLE Derivations and parse trees 6

NLE A more formal definition 7 A CFG is a 4-tuple consisting of NLE What `context free means 8

NLE Derivations and languages The language LG GENERATED by a CFG grammar G is the set of strings of TERMINAL symbols that can be derived from the start symbol S using the production rules in G LG = {w | w is in * and S derives w} The

strings in LG are called GRAMMATICAL The strings not in LG are called UNGRAMMATICAL 9 NLE Grammar development One of the most basic skills in NLE is the ability to write a CFG for some fragment of a

language (e.g., the dates) Well briefly cover some of the issues to be addressed when writing small CFG grammars 10 NLE An example lexicon 11 NLE An example grammar

12 NLE A simple parse tree 13 NLE Basic types of phrases Sentences Noun Phrases Verb phrases

Prepositional phrases 14 NLE Basic types of sentences 15 NLE Noun phases: premodifiers

NP (Det) (Card) (Ord) (Quant) (AP) Nominal Det: Determiners 16 a flight Optional: Im looking for flights to Denver Card: Cardinal numbers (one stop)

Ord: Ordinal numbers (the first flight) Quantifiers: most flights to Denver leave in the morning AP (Adjectives): three very expensive seats NLE Noun phases: postmodifiers Nominal Noun Nominal Nominal PP (PP) (PP) Nominal Nominal GerundVP Nominal Nominal RelClause 17 NLE

Types of postnominal modifiers 18 NLE Recursion Nominal Is an example of RECURSIVE rule Other

Nominal PP (PP) (PP) examples: NP NP PP VP VP PP Recursion a powerful device, but could have bad consequences (see lectures on parsing) 19 NLE

Recursion and VP attachment 20 NLE Coordination NP NP and NP VP VP and VP

John talks softly and carries a big stick S S and / but / S John and Mary left Kim is a lawyer but Sandy is reading medicine. In fact, probably English has a

XP XP and XP rule 21 NLE Agreement This dog Those dogs *This dogs *Those dogs This dog is smart

*This dog are smart *Those dogs is smart 22 NLE CFGs vs Regular languages For many applications, finite state languages (the languages defined by FA) are appropriate Limitation of FAs: cannot count I.e., cannot check A n B n

Example of construction showing that English is CF: long-distance dependencies 24 Which film did Kim say the director who we just met _ recommended _? NLE The Chomsky Hierarchy Finite-state languages (type 3)

Context-free languages (type 2) CAC BB Recursively enumerable languages 25

A BB Context-sensitive languages (type 1) A bC | Cb (a single NT on the right) Every language that can be specified by a finite algorithm NLE Readings Jurafsky

and Martin, chapter 9 The chapters on context-free languages in 26 The Free Dictionary: http://encyclopedia.thefreedictionary.com/Context-fr ee%20language Wikipedia: http://en.wikipedia.org/wiki/Context-free_grammar NLE

Recently Viewed Presentations

  • TRAC Development Workshop 2013 1 The State of

    TRAC Development Workshop 2013 1 The State of

    Gross Change Sum the Avg by category across the years - always start the latest year with the next year after that - example - the vs 2008 needs to start with 2009 pledge (as it's already vs 2008).
  • A Dance With the Butterflies - Susan Silverman

    A Dance With the Butterflies - Susan Silverman

    A Dance With the Butterflies A UDL Showcase ... Free Choice: created models, write stories, drew pictures on paper and on the computer Multiple means of engagement Kid Pix, Microsoft Word, Arts & Crafts Ms. Jacoby's Class Multiple means of...
  • Introduction to Welligent and CASEMIS - WordPress.com

    Introduction to Welligent and CASEMIS - WordPress.com

    Welligent System . Welligent is a District-wide web-based software system used for online IEPs and tracking of related services (such as speech and language, physical therapy, vision and hearing screenings, nursing services, etc.) provided to students during the course of...
  • CIVIL RIGHTS - Economics

    CIVIL RIGHTS - Economics

    CIVIL RIGHTS Brief Legal History of Civil Rights Legislation List of Statues The following list of statues will be organized in the following manner: First the Date Name of the Statue Provisions (and at times comments) Under the Andrew Johnson...
  • Advanced ALU Lecture 5 CS365 RoadMap Implementation of

    Advanced ALU Lecture 5 CS365 RoadMap Implementation of

    Advanced ALU Lecture 5 CS365 RoadMap Implementation of MIPS ALU Signed and unsigned numbers (Section 3.2) Addition and subtraction (Section 3.3) Constructing an arithmetic logic unit (Appendix B.5, B.6) Multiplication (Section 3.4) Division (Section 3.5) Floating point (Section 3.6) Unsigned...
  • Interjections Wow! I got it! tha e r

    Interjections Wow! I got it! tha e r

    Which one shows a strong interjection? Click to check your answer. A Ouch! My finger is hurting. B Oh dear, what have I done? Click to check your answer. The correct answers will highlight. Which sentence shows a mild interjection?...
  • Active Directory Service Accounts

    Active Directory Service Accounts

    What are the differences between a managed service account, a virtual service account, and a group managed service account? Which operating system is required to manage a service with a managed service account?
  • Birds

    Birds

    Birds copyright cmassengale