BCSE409L Natural

Language Processing
Dr. Biji C. L
Associate Professor
Department of Analytics, SCOPE
Module 3: Context Free
Grammar
Context Free Grammar(CFG)
• A language L is called a context-free language (or CFL) if there
is a CFG G such that L = ℒ ( G)
• A CFG is a set of rules (productions) used to group and
organize words and lexicons in a language.
• CFG is a finite collection of rules which tells us that certain
sentences/strings are grammatical and what their grammatical
structure is.
• A context free grammar is one in which all the rules apply
regardless of the context i.e. they would be of the type ‘Rewrite
X as Y’[X → Y], no further conditions being specified.
Key Characteristics
• Formal Grammar: CFG is a type of formal grammar, meaning it
provides a precise mathematical framework for describing the
syntax of languages.
• Phrase-Structure Grammar: CFG is also known as phrase-
structure grammar, and it follows the Backus-Naur Form
(BNF), which is a notation technique for context-free
grammars often used to describe the syntax of languages.
Mathematical Definition
• A CFG is defined as a four-tuple (T, N, S, R), where:
• T (Terminals): The set of terminal symbols (words or tokens)
that appear in the language.
• N (Non-terminals): The set of non-terminal symbols (syntactic
categories) used to define the structure of the language.
• S (Start Symbol): The initial non-terminal symbol from which
the production rules start.
• R (Rules): The set of production rules that define how non-
terminal symbols can be replaced by sequences of non-
terminal and terminal symbols.
Constituents of Grammar
•N (Noun):
•These are words representing people or things Eg: Man, Child
V (Verb):
•This is the action word in the sentence. Example: run, eat, see
•Det (Determiner):
•Determiners are words used before nouns to specify which
noun is being referred to. Eg: "a", "the“
•Adj: Adjective
•Example: big, red, beautiful
•Adv: Adverb
•Example: quickly, silently, very
•Aux: Auxiliary Verb (helping verb)
•Example: is, has, can
•Conj: Conjunction
•Example: and, but, or
•Pron: Pronoun
•Example: he, she, it, they
 Constituents of Grammar

•VP: Verb Phrase

•Often expanded to include more structures
•Example: Aux VP (has eaten), VP Adv (ate quickly)
•C: Complementizer
•Sbar: Subordinate Clause
•Example: that, whether, if
•A clause introduced by a subordinating conjunction or a
•AdjP: Adjective Phrase
relative pronoun
•A phrase with an adjective as the head
•Example: that she knows, whether he left
•Example: very tall, extremely beautiful
•NP: Noun Phrase (additional elements)
•AdvP: Adverb Phrase
•Expanded for possessive constructions
•A phrase with an adverb as the head
•Example: NP’s (the child’s book), Det Adj Noun (the big
•Example: very quickly, incredibly silently
cake)
•PP: Prepositional Phrase (additional elements)
•Expanded to include adverbial phrases
•Example: Pre NP (with the fork), Pre NP PP (in the house
on the hill)
Derive CFG rules "the woman shoots a
man"
1. Start with the start symbol S.
[Link] the rule S → NP VP.
[Link] NP, apply the rule NP → Det N.
1. Det can be "the".
2. N can be "woman".
3. Therefore, NP becomes the woman.
[Link] VP, apply the rule VP → V NP.
1. V can be "shoots".
2. For the second NP, apply the rule NP → Det N.
1. Det can be "a".
2. N can be "man".
3. Therefore, NP becomes a man.
3. Therefore, VP becomes shoots a man.
• Putting it all together, we get the sentence "the woman shoots a man".
An example of CFG
• Here's a simple context free grammar for a small fragment of English:

S -> NP VP
NP -> Det N
VP -> V NP S
/ \
VP -> V
NP VP
Det -> a /\ / | \
Det -> the Det N V Det N
/ \ | | \
N -> woman the woman shoots a man
N -> man
V -> shoots
Ingredients and properties of this
grammar
• What are the ingredients of this grammar?
It contains three types of symbol:
1. ‘->’ = An instruction to rewrite whatever symbol appears to the left of the
arrow as the symbol or string of symbols that appears to the right of the arrow.
2. Symbols written like: S, NP, VP, Det, N, V. These symbols are called non-
terminal symbols. Each of these symbols is shorthand for a grammatical category.
3. Symbols in italics: a, the, woman, man, and shoots. A computer scientist would
probably call these terminal symbols and linguists would probably call them lexical
items.
Rule explanation
• This grammar contains rules.
• Each rule consists of a single non-terminal symbol, followed by ->, followed by a
finite sequence made up of terminal and/or non-terminal symbols.
• We interpret each rule X -> Y as the instruction “rewrite X as Y.”
• For example, rule (2) rewrites the symbol VP as the string of symbols Verb + NP, and
defines Verb + NP to be a construction of the type VP.
• The symbol S (for "sentence") is designated as the initial symbol.
• It is necessary to begin with a rule that has the initial symbol on the left.
• Thereafter any rule may be applied in any order until no further rule is applicable.
Context Free Grammar (contd.)
Consider the string of words – a woman shoots a man.
• Is this grammatical according to our little grammar?
• And if it is, what structure does it have?
The following tree answers both the questions:

Such a tree is called a parse tree, and it gives us two sorts of

information:
1. Information about strings 2. Information about structure
Example: the child ate cake with the fork
• G = (V, T, S, P)
• V = {S, NP, VP, PP, Det, Noun, Verb, Aux, Pre}
• T = {‘a’, ‘ate’, ‘cake’, ‘child’, ‘fork’, ‘the’, ‘with’}
the child ate cake with the fork
• S → NP VP
• → Det Noun VP
• → the Noun VP
• → the child VP
• → the child Verb NP PP
• → the child ate NP PP
• → the child ate Det Noun PP
• → the child ate a Noun PP
• → the child ate a cake PP
• → the child ate the cake P NP
• → the child ate the cake with NP
• → the child ate the cake with Det Noun
• → the child ate the cake with the Noun
• → the child ate the cake with the fork
Note
• Note 1: In P, pipe symbol (|) is used to combine productions into single representation for
productions that have same LHS. For example, Det → ‘a’ | ‘the’ derived from two rules Det → ‘a’ and
Det → ‘the’. Yet it denotes two rules not one.

•
Note 2: The production highlighted in red are referred as grammar, and green are referred as lexicon.

•
Note 3: NP – Noun Phrase, VP – Verb Phrase, PP – Prepositional Phrase, Det – Determiner, Aux –
Auxiliary verb
Problems with CFGs
• A context free language is a language that can be generated by a context free
grammar.
• Some languages are context free, and some are not e.g. it seems plausible that
English is a context free language.
• Some dialects of Swiss-German are not context free.
• It can be proved mathematically that no context free grammar can generate all (and
only) the sentences that native speakers find acceptable and..
• For such dialects, one needs to employ additional grammatical mechanisms, not
merely context free rules.
Phrase Structure Grammar
• It builds up phrases out of words and put the phrases
together into sentences.
• The kind of structural description assigned by a phrase-
structure grammar is, in fact, an immediate constituent
analysis of the sentence.
• It assigns to each sentence that it generates a structural
description.
• It makes use of phrase structure rules.
Phrase Structure Grammar (contd.)

• It enables us to express patterns of grammaticality.

• It provides a structural description to characterize the notion of
grammaticality.
• It provides a way to capture our intuitions about the constituent structure of
sentences
• It also provides a way to explain, or account for, our perceived ambiguity of
certain sentences e.g. “mistrust wounds”
S S
NP VP VP NP

N V V N

Mistrust wounds Mistrust wounds

An example of a Phrase Structure
Grammar
• It generates and thereby defines as grammatical such sentences as "The man will hit
the ball"
An example of a PSG (associated with constituent analysis) :
Derivation of a given sentence
• Interpret each rule X Y as “rewrite X as Y.”
• Derive the sentence “the man hit the ball” using the given grammar :

• The numbers at the right of each line refer to the rule of the grammar used in constructing
that line from the preceding line.
Representation using a Tree Diagram
Inadequacies of Phrase Structure
Grammar
1. Under-generation: Phrase-Structure Grammar often fails to generate all
grammatical sentences in a language, particularly with more complex sentence
structures.
Example: Sentences:
1. He burst into a loud cry and left the room.
[Link] man was bitten by the dog.
[Link] the dog bite the man?
[Link] the man bitten by the dog?
• Explanation:
• PSG struggles to generate questions and passive sentences. The rules in PSG
are often rigid and do not account for the necessary transformations.
• For instance, forming questions requires subject-auxiliary inversion (e.g., "Did
the dog bite the man?") and is not handled by simple PSG rules.
Inadequacies of Phrase Structure
Grammar
• 2. Over-generation
• PSG may generate sentences that are grammatically correct according to its rules
but are semantically nonsensical or ungrammatical in actual language usage.
• Example: Sentences:
1.\The boy died Bill.*
2.\The men would put the book.*
• Explanation:
• While PSG might allow these sentences by applying the rules, they do not make
sense. The verb "died" cannot logically take "Bill" as an object, and "put the
book" is incomplete without a preposition indicating where to put it.
• PSG does not account for semantic constraints or verb-argument structures that
determine the appropriateness of certain combinations.
Inadequacies of Phrase Structure
Grammar
• 3. Lack of Transformational Rules
• PSG lacks the ability to handle certain syntactic transformations necessary
for producing grammatically accurate sentences. Transformational rules are
needed to rearrange phrases correctly.
• Example: Sentence Transformation:
[Link] man was bitten by the dog. (Passive)
[Link] the man bitten by the dog? (Question)
• Explanation:
• PSG does not include rules for moving elements around within a sentence
to form passives or questions. Transformational grammar, introduced by
Chomsky, addresses these issues by incorporating rules that can
manipulate sentence structures dynamically.