Context free grammar examples ppt

removing ambiguity in context free grammar ppt and simplification of context free grammar ppt
Dr.DouglasPatton Profile Pic
Dr.DouglasPatton,United States,Teacher
Published Date:26-07-2017
Your Website URL(Optional)
Comment
CFGs and PCFGs (Probabilistic) Context-Free GrammarsChristopher Manning A phrase structure grammar S  NP VP N  people VP  V NP N  fish VP  V NP PP N  tanks NP  NP NP N  rods NP  NP PP V  people NP  N V  fish NP  e V  tanks PP  P NP P  with people fish tanks people fish with rodsChristopher Manning Phrase structure grammars = context-free grammars (CFGs) • G = (T, N, S, R) • T is a set of terminal symbols • N is a set of nonterminal symbols • S is the start symbol (S ∈ N) • R is a set of rules/productions of the form X  • X ∈ N and ∈ (N ∪ T) • A grammar G generates a language L.Christopher Manning Phrase structure grammars in NLP • G = (T, C, N, S, L, R) • T is a set of terminal symbols • C is a set of preterminal symbols • N is a set of nonterminal symbols • S is the start symbol (S ∈ N) • L is the lexicon, a set of items of the form X  x • X ∈ P and x ∈ T • R is the grammar, a set of items of the form X  • X ∈ N and ∈ (N ∪ C) • By usual convention, S is the start symbol, but in statistical NLP, we usually have an extra node at the top (ROOT, TOP) • We usually write e for an empty sequence, rather than nothingChristopher Manning A phrase structure grammar S  NP VP N  people VP  V NP N  fish VP  V NP PP N  tanks NP  NP NP N  rods NP  NP PP V  people NP  N V  fish NP  e V  tanks PP  P NP P  with people fish tanks people fish with rodsChristopher Manning Probabilistic – or stochastic – context-free grammars (PCFGs) • G = (T, N, S, R, P) • T is a set of terminal symbols • N is a set of nonterminal symbols • S is the start symbol (S ∈ N) • R is a set of rules/productions of the form X  • P is a probability function • P: R  0,1 • • A grammar G generates a language model L. P(g) =1 å g ÎT   Christopher Manning A PCFG S  NP VP 1.0 N  people 0.5 VP  V NP 0.6 N  fish 0.2 VP  V NP PP 0.4 N  tanks 0.2 NP  NP NP 0.1 N  rods 0.1 NP  NP PP 0.2 V  people 0.1 NP  N 0.7 V  fish 0.6 PP  P NP 1.0 V  tanks 0.3 P  with 1.0 With empty NP removed so less ambiguousChristopher Manning The probability of trees and strings • P(t) – The probability of a tree t is the product of the probabilities of the rules used to generate it. • P(s) – The probability of the string s is the sum of the probabilities of the trees which have that string as their yield P(s) = Σ P(s, t) where t is a parse of s j = Σ P(t) jChristopher ManningChristopher ManningChristopher Manning Tree and String Probabilities • s = people fish tanks with rods • P(t ) = 1.0 × 0.7 × 0.4 × 0.5 × 0.6 × 0.7 1 Verb attach × 1.0 × 0.2 × 1.0 × 0.7 × 0.1 = 0.0008232 • P(t ) = 1.0 × 0.7 × 0.6 × 0.5 × 0.6 × 0.2 2 Noun attach × 0.7 × 1.0 × 0.2 × 1.0 × 0.7 × 0.1 = 0.00024696 • P(s) = P(t ) + P(t ) 1 2 = 0.0008232 + 0.00024696 = 0.00107016Christopher ManningChristopher ManningCFGs and PCFGs (Probabilistic) Context-Free GrammarsGrammar Transforms Restricting the grammar form for efficient parsingChristopher Manning Chomsky Normal Form • All rules are of the form X  Y Z or X  w • X, Y, Z ∈ N and w ∈ T • A transformation to this form doesn’t change the weak generative capacity of a CFG • That is, it recognizes the same language • But maybe with different trees • Empties and unaries are removed recursively • n-ary rules are divided by introducing new nonterminals (n 2)Christopher Manning A phrase structure grammar S  NP VP N  people VP  V NP N  fish VP  V NP PP N  tanks NP  NP NP N  rods NP  NP PP V  people NP  N V  fish NP  e V  tanks PP  P NP P  withChristopher Manning Chomsky Normal Form steps S  NP VP N  people S  VP N  fish VP  V NP N  tanks VP  V N  rods VP  V NP PP V  people VP  V PP NP  NP NP V  fish NP  NP V  tanks NP  NP PP P  with NP  PP NP  N PP  P NP PP  PChristopher Manning Chomsky Normal Form steps S  NP VP N  people VP  V NP N  fish S V NP VP  V N  tanks S  V N  rods VP  V NP PP V  people S  V NP PP VP  V PP V  fish S  V PP V  tanks NP  NP NP NP  NP P  with NP  NP PP NP  PP NP  N PP  P NP PP  PChristopher Manning Chomsky Normal Form steps S  NP VP N  people VP  V NP N  fish S V NP VP  V N  tanks VP  V NP PP N  rods S  V NP PP V  people VP  V PP S  V PP S  people NP  NP NP V  fish NP  NP NP  NP PP S  fish NP  PP V  tanks NP  N S  tanks PP  P NP PP  P P  with

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.