SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

UNIT II: Word-Level and Syntactic Analysis

Introduction, Part-of-Speech (POS) Tagging: Rule-Based, Stochastic and Transformation-

Based Approaches, Hidden Markov Models (HMM) and Maximum Entropy Models for POS
Tagging, Context-Free Grammar (CFG) and Constituency Parsing, Treebanks and Normal
Forms for Grammar, Top-Down and Bottom-Up Parsing Strategies, CYK Parsing
Algorithm, Probabilistic Context-Free Grammars (PCFGs), Feature Structures and
Unification.

WORD-LEVEL AND SYNTACTIC ANALYSIS

 Word-level analysis: Tokens, POS tags, morphological structure, and named entities.

 Syntactic analysis: Parses sentence structure using constituency or dependency

grammars.

 Together, they enable machines to understand language structure for various NLP
applications.

1. Introduction
 Word-level analysis deals with understanding individual words, their forms, and
meanings.
 Syntactic analysis (or parsing) deals with sentence structure and grammatical
relationships between words.
 Both are essential for semantic understanding, machine translation, question
answering, and text generation.

2. Word-Level Analysis

1. Tokenization
o Breaking text into words or subwords.
2. Morphological Analysis
o Examining word structure (prefix, root, suffix).
o Includes stemming and lemmatization.
3. Part-of-Speech (POS) Tagging
o Assign grammatical categories to words: noun, verb, adjective, etc.
o Example: "The cat sleeps." → The/DT cat/NN sleeps/VB
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

4. Named Entity Recognition (NER)

o Identify proper nouns like person names, locations, organizations.
o Example: "Barack Obama was born in Hawaii." → Barack Obama/PER,
Hawaii/LOC

3. Syntactic Analysis
 Goal: Understand the structure of sentences and relationships between words.

1. Constituency Parsing (Phrase Structure)

o Represents sentences as nested phrases (NP, VP, etc.)
o Example: "The cat sleeps" → S → NP (The cat) + VP (sleeps)
2. Dependency Parsing
o Represents grammatical relationships as directed links between words.
o Example: "The cat sleeps" → sleeps is head, cat is subject.
3. Grammar Formalisms
o Context-Free Grammar (CFG): Rules like S → NP VP
o Dependency Grammar: Focus on head-dependent relations
4. Applications of Word-Level and Syntactic Analysis
 Machine Translation: Understand structure to preserve meaning.
 Question Answering: Identify subjects, objects, and relations.

 Information Extraction: Extract structured data from unstructured text.

 Text Summarization: Analyze sentence structure for key points.

 Spell Checking & Grammar Correction: Detect structural errors.

5. Challenges
 Ambiguity: Words can have multiple POS tags.

o Example: "Book a flight" vs "Read a book"

 Complex Sentences: Handling nested or long sentences.

 Free Word Order Languages: Harder parsing for languages like Hindi or Japanese.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

 Resource Scarcity: Limited annotated corpora for many languages.

PART-OF-SPEECH (POS) TAGGING

POS tagging is a key step in NLP pipelines that labels each word with its grammatical category.
Techniques range from rule-based to deep learning, and it is crucial for parsing, translation,
and semantic understanding.

1. Introduction
 POS Tagging is the process of assigning grammatical categories (noun, verb, adjective,
etc.) to each word in a sentence.
 It is a fundamental step in NLP for:

o Syntactic parsing
o Information extraction
o Machine translation
o Question answering
2. Common POS Tags
 Noun (NN): cat, book, city

 Proper Noun (NNP): John, India

 Verb (VB): run, eat

 Adjective (JJ): big, red

 Adverb (RB): quickly, very

 Determiner (DT): the, a, an

 Pronoun (PRP): he, she, it

 Preposition (IN): in, on, at

 Conjunction (CC): and, or, but

Example:
Sentence: "The cat sleeps on the mat."
POS Tagged: The/DT cat/NN sleeps/VB on/IN the/DT mat/NN ./.

3. Techniques for POS Tagging

 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

1. Rule-Based Tagging
o Uses hand-crafted linguistic rules and dictionaries.
o Example Rule: If a word ends with -ing → likely a verb.
2. Stochastic / Probabilistic Tagging
o Uses statistical models like Hidden Markov Models (HMMs).
o Assigns tags based on probability of a sequence: P(tag|previous tag).

3. Transformation-Based Tagging
o Uses Brill’s tagger: learns rules from annotated corpora.
4. Neural Network / Deep Learning Models
o LSTM, Bi-LSTM, Transformers (BERT-based taggers)
o Capture long-range dependencies and context.
4. Applications of POS Tagging
 Parsing & Grammar Checking: Identifies structure and grammatical errors.

 Information Extraction: Extracts entities, relations, and facts.

 Machine Translation: Helps preserve syntactic structure across languages.

 Text-to-Speech Systems: Determines correct pronunciation (e.g., “lead” as noun vs

verb).
 Word Sense Disambiguation: Helps infer meaning using syntactic context.

5. Challenges
 Ambiguity: Words with multiple possible tags.

o Example: "Can" → verb or modal auxiliary?

 Unknown Words: Words not present in the training corpus.

 Domain Variation: POS patterns differ across text types (news, social media, medical
text).
 Free Word Order Languages: Complexity increases for languages like Hindi or
Japanese.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

RULE-BASED POS TAGGING

Rule-Based POS tagging relies on a dictionary + handcrafted linguistic rules to assign
grammatical categories. While interpretable and useful for small-scale systems, it struggles with
ambiguity and scalability.

1. Introduction
 Rule-Based POS Tagging assigns a part-of-speech (POS) to each word in a sentence
using:
1. Lexical knowledge (dictionary of words and possible tags)

2. Hand-crafted linguistic rules

 One of the earliest POS tagging methods, especially before statistical approaches
became common.

2. Components of a Rule-Based Tagger

1. Lexicon / Dictionary
o A list of words and their possible POS tags.
o Example:
 "book" → noun, verb

 "run" → noun, verb

2. Rules
o Linguistic rules applied to resolve ambiguity.
o Types of rules:
 Contextual Rules: Use surrounding words to decide the tag.

 Example: If a word follows a determiner (DT), tag it as a noun

(NN).
 Morphological Rules: Use word suffix/prefix patterns.
 Example: Words ending in -ing → verb (VBG).
 Fallback Rules: Default to the most common tag in lexicon if no other
rules apply.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
3. Working of a Rule-Based Tagger
1. Look up each word in the dictionary for possible POS tags.

2. Apply disambiguation rules based on context or morphology.

3. Assign the most appropriate tag to each word.

Example:
Sentence: "The cat sleeps on the mat."

 Lexicon lookup:
o "The" → DT
o "cat" → NN
o "sleeps" → VB, NNS
 Rule application:

o If previous word = DT, current word = NN → "cat" tagged as NN

o "sleeps" follows NN → likely VB → tagged as VB
Output: "The/DT cat/NN sleeps/VB on/IN the/DT mat/NN ./"

4. Advantages

 No training data required

 Can be very accurate for well-defined domains

 Easy to interpret and debug

5. Disadvantages
 Labor-intensive: Rules must be manually crafted for each language.

 Limited coverage: Cannot handle all lexical ambiguities or unknown words.

 Not scalable for large corpora or multiple languages.

 Context limitation: Cannot capture long-range dependencies like neural models.

6. Applications
 Early POS tagging systems in English and other languages.
 Useful in domain-specific NLP systems where training data is scarce.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Basis for hybrid systems combining rule-based + statistical models.

STOCHASTIC (PROBABILISTIC) POS TAGGING

1. Introduction
 Stochastic POS Tagging assigns part-of-speech tags based on probabilities derived
from annotated corpora.
 It is also called statistical POS tagging.

 Uses contextual information to resolve ambiguities that rule-based methods may fail to
handle.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

5. Advantages
 Can handle ambiguous words using context.

 Learns from data, adaptable to new domains.

 Scalable for large corpora and multiple languages.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

6. Disadvantages
 Requires annotated corpora for training.

 Probabilities may be sparse for rare words or sequences.

 Cannot capture long-range dependencies without advanced models.

7. Applications
 POS tagging in large-scale corpora

 Syntactic parsing

 Machine translation

 Speech recognition
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

Step 5: Interpretation
 The Viterbi algorithm chooses the most probable tag sequence based on:

1. Transition probabilities (grammar context)

2. Emission probabilities (likelihood of word given tag)

 Final tagging respects both word meaning and syntactic context.

Word Tag Viterbi Probability Previous Tag

The DT 1 –

cat NN 0.4 DT

sleeps VB 0.168 NN

TRANSFORMATION-BASED POS TAGGING (BRILL TAGGER)

 Transformation-Based POS Tagging starts with an initial tagging, then iteratively
corrects errors using learned rules from training data.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 It is interpretable, accurate, and widely used in hybrid NLP systems.

1. Introduction
 Transformation-Based Learning (TBL) is a hybrid approach to POS tagging.

 Introduced by Eric Brill (1992).

 Combines the accuracy of rule-based tagging with learning from annotated corpora.

 Tags are initially assigned using a simple method, then iteratively improved by
applying learned transformations.

2. Core Idea
1. Start with initial tags (e.g., from a lexicon or default most frequent tag).

2. Learn rules that correct errors in the tagged text using a training corpus.

3. Apply the learned transformation rules to new text.

 Each transformation rule has the form:

“Change tag X to Y when the word’s context satisfies condition C.”

3. Example of Transformation Rules

 Initial tagging: Most frequent tag per word

 Transformation rules learned from data:

1. Change NN → VB if the previous word is "to"
 Example: "to run" → run/VB

2. Change NN → JJ if the next word is "car"

 Example: "fast car" → fast/JJ car/NN

3. Change VB → NN if the word ends with -ing and previous word is the

4. Advantages
 High accuracy: Can approach state-of-the-art POS tagging performance.

 Interpretable rules: Each rule is readable and understandable.

 Requires less data than fully statistical methods.

 Combines advantages of rule-based and statistical approaches.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
5. Disadvantages
 Training can be time-consuming for large corpora.

 May not generalize well to highly different domains.

 Complexity increases if too many rules are learned.

6. Applications
 POS Tagging in English and other languages.

 Basis for hybrid NLP systems that combine rules and statistical models.
 Useful for error correction in tagging ambiguous or rare words.

HIDDEN MARKOV MODELS (HMM)

 HMMs model sequential data in NLP where the observations (words) are visible but
states (tags) are hidden.
 Core components: transition, emission, and initial probabilities.
 The Viterbi algorithm decodes the best sequence of hidden states.

1. Introduction
 HMMs are statistical models for sequences where the system is assumed to be a
Markov process with hidden states.

 Widely used in NLP tasks such as:

o POS tagging
o Speech recognition
o Named Entity Recognition (NER)
 Key idea: We observe outputs (words), but the underlying states (tags) are hidden.

2. Components of an HMM
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

5. Advantages
 Captures sequential dependencies between tags.
 Probabilistic approach handles ambiguity naturally.
 Can be trained from annotated corpora.

6. Disadvantages
 Assumes Markov property (current state depends only on previous state), ignoring long-
range dependencies.
 Emission probabilities may be sparse for rare words.
 Requires large annotated corpora for accurate parameter estimation.

7. Applications
 POS Tagging
 Speech Recognition
 Named Entity Recognition (NER)
 Machine Translation (alignment modeling)
 Bioinformatics (gene sequence modeling)
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Each cell in the Viterbi lattice = probability of best path ending in that tag.

 Transition probabilities = likelihood of one tag following another.

 Emission probabilities = likelihood of a word being generated by a tag.

 The Viterbi algorithm combines these to find the most probable sequence.
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

Step 5: Interpretation
1. Start with initial probability of first tag.

2. Multiply previous Viterbi probability × transition probability × emission probability at

each step.
3. Choose the maximum probability path at each step.

4. Trace back to get the most likely sequence of POS tags.

MAXIMUM ENTROPY (MAXENT) MODELS FOR POS TAGGING

 MaxEnt models compute probabilities of tags using rich features from words and
context.
 Tag with maximum probability is assigned.
 Advantages over HMM: flexible, feature-rich, no strong independence assumptions.

1. Introduction
 Maximum Entropy Models are probabilistic models used in NLP for sequence labeling
tasks like POS tagging.
 Based on the principle of maximum entropy: among all probability distributions
satisfying given constraints, choose the one with highest entropy (most uniform / least
biased).
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Advantages: Can incorporate diverse features, not limited to sequential dependencies like
HMMs.

3. Features Used in POS Tagging

MaxEnt models allow rich features, such as:

1. Lexical Features
o Current word, suffixes, prefixes, capitalization
o Example: If word ends in -ing, likely VB
2. Contextual Features
o Previous and next words or tags
o Example: If previous word = to, current word → VB
3. Orthographic Features
o Numbers, hyphens, punctuation
o Example: If word contains digits → NN (numeric)
4. Combined Features
o Previous tag + current word, word shape, etc.
4. How MaxEnt POS Tagging Works
1. Training Phase
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
o Input: Annotated corpus (words + correct tags)
o Learn weights (λi\lambda_iλi) for each feature to maximize likelihood
2. Tagging Phase
o For each word:
 Extract features from word and context
 Compute probabilities of all possible tags

 Assign tag with highest probability

5. Example
Sentence: "The cat sleeps"

Features for "sleeps":

 Current word = "sleeps"

 Previous word = "cat"

 Previous tag = "NN"

 Word suffix = "ps"

Compute probability for each candidate tag:

 P(VB | features) = 0.75

 P(NN | features) = 0.10

 P(JJ | features) = 0.05

→ Assign VB as tag for "sleeps" because it has highest probability.

6. Advantages
 Can incorporate arbitrary, overlapping features.
 Does not require independence assumptions like HMMs.

 Often achieves higher accuracy in POS tagging than HMMs.

7. Disadvantages
 Computationally more expensive than HMMs for large feature sets.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Requires good feature engineering (though deep learning reduces this need).

 Needs a large annotated corpus for robust performance.

8. Applications
 POS Tagging (main application)

 Named Entity Recognition (NER)

 Chunking / Shallow Parsing

 Information Extraction
CONTEXT-FREE GRAMMAR (CFG)
 CFG is a formal grammar with rules defining how sentences are structured.

 Consists of non-terminals, terminals, production rules, and a start symbol.

 Widely used in parsing and syntactic analysis in NLP.

 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

1. Introduction
 CFG is a formal grammar used to describe syntactic structures of languages.

 Widely used in parsing sentences, syntactic analysis, and compiler design.

 A CFG consists of rules that describe how sentences can be generated from a set of
symbols.
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
6. Advantages of CFG
 Can model hierarchical structure of sentences.

 Supports automated parsing.

 Useful in NLP tasks like POS tagging, syntax checking, and machine translation.

7. Limitations of CFG
 Cannot easily handle long-distance dependencies (e.g., subject-verb agreement across
clauses).
 May not capture all linguistic nuances, especially in free-word-order languages.
 Ambiguity can lead to multiple parse trees for the same sentence.

8. Applications in NLP

 Syntactic parsing

 Grammar checking

 Machine Translation

 Question Answering

 Information Extraction
CONSTITUENCY PARSING
 Constituency Parsing identifies phrases and their hierarchical relationships in a
sentence.

 Uses CFG or probabilistic methods to generate a parse tree.

 Provides structured syntactic information for various NLP tasks.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

1. Introduction
 Constituency Parsing (or Phrase Structure Parsing) analyzes a sentence to identify its
constituent parts, such as noun phrases (NP), verb phrases (VP), and prepositional
phrases (PP).
 Based on Context-Free Grammar (CFG).

 Helps machines understand hierarchical structure of sentences.

SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

6. Advantages
 Captures hierarchical and phrasal structure.

 Useful for machine translation, summarization, and question answering.

 Provides interpretable syntactic analysis.

7. Limitations
 Ambiguity: Sentences may have multiple valid parse trees.
 Complexity: Parsing long sentences can be computationally expensive.

 Less effective for free-word-order languages unless probabilistic or neural methods are
used.

8. Applications
 Syntactic analysis for NLP pipelines.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Machine Translation: Helps maintain sentence structure.

 Question Answering & Information Extraction: Identify subject, object, and phrases.

 Grammar Checking & Correction

TREEBANKS AND NORMAL FORMS FOR GRAMMAR

 Treebanks: Annotated corpora with POS tags and parse trees for training and evaluation.

 Normal forms: Standardized representations of grammar rules (CNF, GNF) to simplify

parsing.
 Both are essential for building and evaluating NLP parsing systems.

1. Treebanks

Definition:

 A treebank is a corpus of sentences annotated with syntactic or semantic parse trees.

 Provides gold-standard examples for training and evaluating parsers.

Purpose in NLP:
 Helps train statistical parsers.

 Used in POS tagging, syntactic parsing, and grammar evaluation.

 Enables comparative evaluation of parsing algorithms.

Examples of Treebanks:
1. Penn Treebank (PTB) – English, widely used in NLP research.

2. Universal Dependencies (UD) Treebanks – multilingual, dependency-based annotation.

3. NEGRA Treebank – German, constituency-based.

Structure:
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Each sentence is annotated with:

o POS tags for each word

o Phrase structure or dependency structure
 Stored as bracketed trees or dependency graphs

Example (Bracketed):
Sentence: "The cat sleeps"
(S

(NP (DT The) (NN cat))

(VP (VB sleeps))

2. Normal Forms for Grammar

Definition:

 Normal forms are standardized ways to represent grammar rules.

 Simplify parsing and grammar analysis.

Common Normal Forms:

1. Chomsky Normal Form (CNF)

o Each production rule is either:
1. A → BC (two non-terminals)
2. A → a (a single terminal)
o Example:
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Original: S → NP VP

 CNF: S → X VP, X → NP

2. Greibach Normal Form (GNF)

o Each production starts with a terminal followed by zero or more non-terminals.
o Example: S → aA B
Why Normal Forms Are Useful:
 Simplify parsing algorithms (like CYK parser uses CNF).

 Reduce ambiguity and complexity in automated parsing.

 Facilitate formal proofs and computational efficiency.

3. Applications in NLP

 Treebanks
o Train and evaluate statistical and neural parsers.
o Serve as gold-standard datasets.
 Normal Forms
o Simplify syntactic parsing algorithms.
o Used in compiler design, CFG parsing, and NLP education.
TOP-DOWN AND BOTTOM-UP PARSING STRATEGIES
Parsing strategies determine how a parser constructs a parse tree for a sentence based on a
grammar. The two main strategies are Top-Down and Bottom-Up Parsing.

 Top-Down Parsing: Start from root, expand non-terminals, match input.

 Bottom-Up Parsing: Start from input tokens, combine into constituents, reach root.
 Both produce the same parse tree but follow opposite directions.

1. Top-Down Parsing
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

Definition:
 Top-Down Parsing starts from the start symbol (S) and tries to derive the input
sentence by recursively expanding non-terminals using grammar rules.
 Works from root to leaves of the parse tree.

Characteristics:
 Predictive approach: tries to match input tokens by applying rules.

 Can use lookahead to reduce backtracking (e.g., in LL parsers).

 Can suffer from left recursion and may require grammar modification.
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

3. Bottom-Up Parsing

Definition:
 Bottom-Up Parsing starts from the input sentence (leaves) and tries to construct the
parse tree up to the start symbol.

 Works from leaves to root.

Characteristics:
 Data-driven approach: combines words into phrases, then phrases into sentences.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Avoids left-recursion problems.

 Can be implemented using shift-reduce parsers.

Feature Top-Down Parsing Bottom-Up Parsing

Approach Root → Leaves (Start → Input) Leaves → Root (Input → Start)

Predictive Yes No

Handles Left Recursion Poor Good

Backtracking Needed Often Sometimes

Example Implementation Recursive Descent, LL Parser Shift-Reduce, LR Parser

4. Applications
 Top-Down Parsing: Suitable for predictive parsers and simple CFGs.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 Bottom-Up Parsing: Used in LR parsers, shift-reduce parsers, and large-scale NLP
parsing systems.
 Both strategies are foundational for syntactic analysis, machine translation, and
grammar checking.

CYK PARSING ALGORITHM

CYK (Cocke–Younger–Kasami) Parsing Algorithm

 CYK Algorithm is a bottom-up parser using CNF CFGs.
 Fills a triangular table with non-terminals that generate substrings.
 Efficiently checks sentence validity and can construct parse trees.

1. Introduction
 CYK Algorithm is a bottom-up parsing algorithm for Context-Free Grammars
(CFG).
 Works only with grammars in Chomsky Normal Form (CNF).

 Efficiently determines if a sentence can be generated by a CFG and produces a parse

tree.
 Widely used in NLP for syntactic parsing.
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

7. Applications
 Syntactic parsing in NLP

 Grammar checking
 Machine translation

 Bioinformatics (sequence parsing)

PROBABILISTIC CONTEXT-FREE GRAMMARS (PCFGS)

 PCFGs = CFG + probabilities.

 Probabilities allow choosing the most likely parse among multiple possibilities.

 Essential in statistical NLP for disambiguation and robust parsing.

1. Introduction
 PCFGs are an extension of Context-Free Grammars (CFGs) that assign probabilities
to production rules.
 Used to handle ambiguity in natural language, e.g., multiple parse trees for a sentence.
 Widely used in statistical parsing, machine translation, and speech recognition.
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

5. Advantages
 Handles ambiguity by selecting the most probable parse.
 Can be trained from treebanks to capture real-language usage.
 Provides a probabilistic ranking of parse trees.

6. Disadvantages
 Accuracy depends on quality and size of annotated corpus.

 Assumes independence of rules, which may not capture long-range dependencies.

 Computationally more expensive than CFG parsing.

7. Applications
 Statistical Syntactic Parsing (disambiguation of multiple parse trees)

 Machine Translation (syntax-based translation)

 Speech Recognition (probable syntactic structure for word sequences)

 Information Extraction (finding structured information from text)
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II

FEATURE STRUCTURES AND UNIFICATION

 Feature structures: Attribute-value pairs representing linguistic info.

 Unification: Merging FS consistently; fails if conflicts exist.

 Essential for agreement checking, parsing, and constraint-based grammar systems.

1. Introduction
 Feature Structures (FS) are a way to represent rich linguistic information about
words, phrases, or syntactic categories.
 Common in unification-based grammars like Head-Driven Phrase Structure
Grammar (HPSG).
 They help encode syntactic, semantic, morphological, and agreement information
compactly.

2. What is a Feature Structure?

 A feature structure is essentially a set of attribute-value pairs.

 Example: For the word "dogs":

[

CATEGORY: Noun
NUMBER: Plural
PERSON: 3rd
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
GENDER: Neutral

 Attributes = CATEGORY, NUMBER, PERSON, GENDER

 Values = Noun, Plural, 3rd, Neutral

 Can also include nested feature structures, e.g., for a verb phrase:

[
CATEGORY: VP
HEAD: [ CATEGORY: V, TENSE: Present, NUMBER: Singular ]

SUBJ: [ CATEGORY: NP, NUMBER: Singular ]

3. Unification
 Unification is the process of merging two feature structures consistently.

 If two structures agree on shared features, they are unified.

 If they conflict, unification fails.

4. Example of Unification

FS1 (Subject NP):

[ CATEGORY: NP, NUMBER: Singular ]

FS2 (Verb VP Head):
[ CATEGORY: V, NUMBER: Singular ]

Unifying NP and VP features for agreement:

 Both have NUMBER = Singular → compatible → unification succeeds.

 If VP had NUMBER = Plural → conflict → unification fails.

5. Advantages of Feature Structures

1. Expressive – Can capture multiple linguistic properties in one structure.
2. Handles agreement constraints – E.g., subject-verb agreement.
 SREENIVASA INSTITUTE OF TECHNOLOGY AND MANAGEMENT STUDIES,
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
III [Link] II SEMESTER CSE R23 REGULATION
LECTURE NOTES
NATURAL LANGUAGE PROCESSING (23CAI353T)
UNIT II
3. Supports modular grammars – Features can be added or reused.

4. Basis for unification-based parsers – Widely used in HPSG, LFG, and TAG.

6. Applications in NLP
 Syntactic parsing – unification ensures features match across constituents.

 Morphological analysis – number, gender, tense, person.

 Semantic interpretation – features can include semantic roles.

 Constraint-based grammars – HPSG, Lexical Functional Grammar (LFG).