1.

Grammars for Natural Language

Grammar in NLP is a set of formal rules that describe how words combine to form
valid sentences in a language.
Importance:
Grammar is important because it helps a system understand the structure and meaning
of sentences, enabling correct parsing and language interpretation.

Helps distinguish meaning:

“Dog bites man” ≠ “Man bites dog”
Essential for:
 Machine Translation
 Question Answering
 Chatbots
 Information Extraction

Grammar transforms linear text → hierarchical structure.

Also, A grammar specifies:

 Valid word combinations
 Phrase structure
 Hierarchical relationships

It acts as a formal rule system.

Parsing is the process of analyzing a sentence to determine its grammatical structure

according to a given grammar.
Role of the CKY algorithm:
The CKY algorithm is a bottom-up dynamic programming method used to
efficiently parse sentences using a Context-Free Grammar (in Chomsky Normal
Form) by filling a chart to check whether the sentence can be generated by the
grammar.
2. Types of Grammars in NLP

1) Context-Free Grammar (CFG)

Definition:
A grammar that uses production rules of the form:

Where:
A, B, C = Non-terminals (like NP, VP, S)
 a = Terminal (actual word)
Purpose:
Used for modeling phrase structure of sentences.
Example Sentence:
The cat eats fish.
Example CFG Rules:
S → NP VP
NP → Det N
VP → V NP
Det → the
N → cat | fish
V → eats
How it works:
The grammar builds structure like:
S
/ \
NP VP
/ \ / \
Det N V NP
the cat eats fish
Good for modeling hierarchical phrase structure.
Cannot easily handle long-distance dependencies.

2) Dependency Grammar
Definition:
Focuses on word-to-word relationships instead of phrase structure.
Each word (except root) depends on another word.
Example Sentence:
The cat eats fish.
Dependencies:
eats → cat (subject)
eats → fish (object)
cat → The (determiner)
Representation (Dependency Tree):
eats
/ \
cat fish
|
The
Good for capturing syntactic relations.
Useful in machine translation and information extraction.

3) Probabilistic Grammar (PCFG)

Definition:
A CFG where each rule has a probability.
Used to resolve ambiguity.
Example Ambiguous Sentence:
I saw the man with a telescope.
Two possible meanings:
I used a telescope.
The man had a telescope.

Example Rules with Probabilities:

VP → V NP (0.7)
VP → VP PP (0.3)
NP → NP PP (0.4)
The parse with higher total probability is chosen.
Formula:

Helps choose the most likely interpretation.

Challenges in Grammar-Based Parsing

 Structural ambiguity
 Low-resource languages
 Integration with semantics
 Long-distance dependencies

3. Movement Phenomenon in Language

Movement = A syntactic transformation where a constituent appears displaced from

its original position.
Leaves behind a trace (gap).
Example:
Which book did Mary read ___?

Types of Movement
Type Example
Subject-Aux Inversion She is singing → Is she singing?
Wh-Movement She bought a book → What did she buy?
Topicalization I love chocolate → Chocolate, I love
Clefting It was Mary who wrote the report
 Type Example
Passivization An award was given
Heavy NP Shift The man donated his money who won

Auxiliary inversion is a type of movement where the helping verb (auxiliary) moves
before the subject to form a question.
Example:
She is coming. → Is she coming?
Wh-Movement
Wh-Movement is when a question word (what, who, where, etc.) moves to the
beginning of the sentence to form a question.
Example:
She bought a book. → What did she buy?

Topicalization
Topicalization is when an important word or phrase is moved to the beginning of a
sentence for emphasis.
Example:
I like this movie. → This movie, I like.

Clefting
Clefting is when a sentence is divided into two parts to emphasize a particular
element.
Example:
John broke the vase. → It was John who broke the vase.

Passivization
Passivization is when the object of a sentence moves to the subject position and the
verb changes to passive form.
Example:
The teacher praised the student. → The student was praised by the teacher.

Heavy NP Shift
Heavy NP Shift is when a long noun phrase is moved to the end of the sentence for
better clarity or balance.
Example:
She gave to her friend a very beautiful handmade birthday gift. →
She gave a very beautiful handmade birthday gift to her friend.
Constraints in Movement (NLP – Syntax):
Restrictions on how elements can move in a sentence (e.g., wh-movement). Example:
“What did you buy?” is correct, but movement cannot violate structure constraints
like subjacency.
Diagnostics in Movement:
Tests used to check syntactic movement, such as question formation, passivization,
cleft sentences, and topicalization to verify constituent structure.
Computational Challenges in NLP:
Handling syntactic ambiguity, long-distance dependencies (movement), data sparsity,
high memory/time complexity, and efficient parsing of large corpora.

4. Handling Questions in Context-Free Grammars

Handling questions in Context-Free Grammar (CFG) involves modifying grammar

rules to represent special syntactic structures found in interrogative sentences. In
English, question formation mainly includes auxiliary inversion and wh-movement.
In declarative sentences, the normal word order is:
S → NP VP
Example:
She is coming.
But in questions, the word order changes. Therefore, CFG rules must be extended to
correctly generate and parse interrogative forms.

Yes/No Questions (Auxiliary Inversion)

In yes/no questions, the auxiliary verb moves before the subject.
Example:
She is coming. → Is she coming?
To represent this in CFG, we add a rule:
S → Aux NP VP
VP → V | V NP
Here, the auxiliary (is) appears before the noun phrase (she).
This rule allows the grammar to generate correct yes/no questions.
If there is no auxiliary, English uses “do-support”:
You like coffee. → Do you like coffee?
So we may include:
S → Aux NP V
Aux → do | does | did | is | are

Wh-Questions (Wh-Movement)
Wh-questions begin with words like what, who, where, when, why, how.
Example:
You bought what. → What did you buy?
In CFG, rules can be modified as:
S → Wh Aux NP VP
 Wh → what | who | where | when | why | how
This accounts for movement of the wh-word to the front of the sentence.

Structural Representation
CFG separates sentence types as:
Declarative: S → NP VP
Yes/No Question: S → Aux NP VP
Wh-Question: S → Wh Aux NP VP
Thus, separate production rules are introduced to handle different interrogative
structures.

Importance in NLP
Handling questions in CFG is essential for:
 Syntactic parsing
 Question answering systems
 Chatbots and dialogue systems
 Machine translation

However, modeling long-distance dependencies (like wh-movement) increases

computational complexity and may require advanced grammars beyond simple CFG.

Limitations of CFG in Handling Questions

Cannot properly handle long-distance dependencies (wh-movement gaps)
Overgeneration of ungrammatical question forms

Why Questions Are Difficult in CFG

Questions are difficult in CFG because they involve movement (like wh-words and
auxiliary inversion), and basic CFG cannot easily represent long-distance
dependencies or gaps left after movement.
Therefore, more advanced mechanisms like hold mechanisms in ATNs are
introduced to properly handle such movements and maintain grammatical
relationships.

5. Hold Mechanisms in ATNs

An Augmented Transition Network (ATN) is an extension of a Recursive Transition

Network used in NLP for syntactic parsing. It includes registers, tests, conditions, and
stack operations to handle complex sentence structures such as embeddings and long-
distance dependencies.
The hold mechanism in ATN is used to temporarily store information while parsing
and retrieve it later when required.
Hold Mechanism – Definition
The hold mechanism allows the parser to:
 Store partial parse information.
 Suspend current processing.
 Return to the stored state later.

It is mainly implemented using stack operations (PUSH and POP).

Stack Operations in ATN

(a) PUSH Operation
Definition:
PUSH saves the current parsing state (including node position, registers, and
remaining input) onto the stack and transfers control to another subnetwork.
Purpose:
 To handle embedded or recursive structures.
 To preserve context before entering a sub-structure.

Simple Example:
Sentence:
The boy who is running is happy.
While parsing “who is running,” the parser:
PUSHES the main sentence state onto the stack.
Enters the relative clause subnetwork.

(b) POP Operation

Definition:
POP retrieves the previously saved state from the stack and resumes parsing from that
point.
Purpose:
 To return to the main sentence after completing a sub-structure.
 To restore stored context.

Continuing Example:
After parsing “who is running”:
The parser POPS the stored state.
Continues parsing “is happy.”

Context Preservation
Definition:
Context preservation means maintaining grammatical information (subject, tense,
agreement, partial tree structure) while processing embedded or complex
constructions.
In ATN:
 Registers store features (e.g., number, tense).
 Stack preserves these registers during recursion.

Example:
Sentence:
The girl said that the boy left.
When entering the clause “that the boy left”:
 The parser PUSHES the outer sentence context.
 Parses the embedded clause.
 POPS back to complete the main sentence.

Thus, context is not lost.

Advantages of Hold Mechanisms in Parsing
 Handles recursive and embedded structures efficiently.
 Preserves grammatical context during subnetwork processing.
 Supports long-distance dependencies.
 Reduces ambiguity through structured control flow.
 Makes parsing of natural language more flexible and powerful compared to
simple CFG.

6. Gap Threading

Gap threading is a technique used in parsing to pass information about a missing

element (gap) through different parts of a sentence until it is correctly linked to the
moved word.
Example:
What did she buy __ ?
The parser keeps track of the gap after “buy” and connects it to the moved word
“what.”

Gap Threading and Difference Lists –

Gap threading is a technique used in NLP parsing to pass information about a
missing element (gap) through intermediate structures until it reaches its correct
grammatical position.
It is mainly used to handle wh-movement in questions.
Example:
What do you think she bought ___?
Here, “what” is moved to the front, and its original object position after “bought”
becomes a gap.
The gap information passes through:
 Main clause → What do you think…
 Embedded clause → …she bought…
 Final verb position → gap after bought

Thus, the parser keeps track of the missing noun phrase until it reaches the correct
location.

Difference Lists – Definition

Difference lists are used to represent and track gap flow efficiently during parsing.
They represent the input state and the remaining state after parsing.
Notation examples:
np(F-F) → No gap present
np([gap(np)|F]-F) → Gap introduced
vp(In-Out) → Gap state changes while parsing
Difference lists help:
 Pass gap information through rules
 Maintain consistency between moved elements and gap positions

They efficiently model long-distance dependencies.

Applications
 Question Answering Systems
 Chatbots
 Machine Translation
 Semantic Role Labeling

7. Human Preferences in Parsing

Human sentence parsing is influenced by several cognitive factors such as:

 Context
 Experience
 Probability
 Cognitive constraints

Example:
I cut the bread with a knife.
Humans naturally prefer the interpretation where “knife” is the instrument (not
something attached to bread). This preference is based on real-world knowledge and
semantic plausibility.

Sources of Preference
Semantic plausibility – Meaningful interpretations are preferred.
 Simplicity – Simpler structures are favored.
Experience – Past exposure influences interpretation.
Cultural background – Interpretation may vary across cultures.
Working memory limits – Humans prefer structures that are easier to
process.

Interpretable Preference Modeling

Goal:
To make parsing decisions explainable in NLP systems.
A system should:
 Show alternative parses
 Display probability scores
 Reveal feature importance
 Provide reasoning signals

This improves transparency and trust in AI models.

Risks
 Human bias
 Annotation inconsistency
 Cultural skew
 Overfitting to specific datasets

Future Directions
 Human-centered models
 Cognitive-inspired architectures
 Cross-linguistic adaptation
 Context-aware parsing

Thus, modeling human preferences helps NLP systems produce more natural,
accurate, and explainable parsing decisions.

8. Shift-Reduce Parsers

Shift–reduce parsing is a bottom-up parsing technique used in syntax analysis. It

builds the parse tree from the input words (leaves) up to the start symbol by
repeatedly applying grammar rules.
It works with a stack and an input buffer, processing the sentence from left to right.

Core Operations
(1) Shift
Definition:
Shift operation moves the next input word from the input buffer onto the stack.
Purpose:
To read and store input symbols for further reduction.

(2) Reduce
Definition:
Reduce operation replaces a sequence of symbols on the stack (right-hand side of a
grammar rule) with a non-terminal symbol (left-hand side).
Purpose:
To combine words/phrases according to grammar rules and move toward the start
symbol.

Working Example
Sentence:
“The dog barks”
Grammar Rules:
S → NP VP
NP → Det N
VP → V
Det → The
N → dog
V → barks

Step-by-Step Parsing
Initial:
Stack: (empty)
Input: The dog barks
Shift → The
Reduce → Det
Shift → dog
Reduce → N
Reduce → NP (Det N)
Shift → barks
Reduce → V
Reduce → VP
Reduce → S (NP VP)
Final Stack:
S → Parsing successful
Thus, the sentence is successfully reduced to the start symbol S.
Advantages
 Linear time complexity (efficient for many grammars)
 Memory efficient (uses stack-based processing)
 Suitable for real-time systems
 Simple implementation

Challenges
Shift–Reduce Conflict:
Parser cannot decide whether to shift or reduce.
Reduce–Reduce Conflict:
Parser cannot decide which grammar rule to apply.
Error Propagation:
Early mistakes affect later parsing.
Limited Lookahead:
Cannot see far ahead in input.
Ambiguity Handling:
Difficult to handle multiple valid parses.

9. Deterministic Parsers

A deterministic parser is a parser that makes only one fixed decision at each step
without backtracking.
Example:
For the sentence:
She eats apples.
The parser reads from left to right and deterministically applies rules like:
NP → She
VP → eats apples
S → NP VP
It follows one clear path without trying multiple alternatives.
Advantages:
 Fast and efficient.
 Uses less memory.
 Suitable for real-time applications.

Example
“The dog runs”
Parser:
Reads
Reduces
 Builds structure
Single fixed path

Deterministic vs Non-Deterministic
Sentence:
“The boy saw the girl with a telescope.”
Deterministic:
Chooses one interpretation only.
Non-deterministic:
Keeps both:
Instrument attachment
Noun attachment

Advantages
 Faster
 Low memory
 Predictable
 Scalable

Applications
 Chatbots
 Voice assistants
 Grammar checkers
 Information extraction
 Compilers

Final Conceptual Summary

Concept Core Idea
Grammar Structural rules of language
Movement Displacement of constituents
Questions in CFG Require extra inversion rules
Hold Mechanism Temporary storage of moved elements
Gap Threading Passing missing element info
Human Preferences Probabilistic, context-based interpretation
Shift-Reduce Efficient bottom-up parsing
Deterministic Parsing Single-path parsing