PART 1 — Questions 1–5

Q1. Define Natural Language Processing (NLP). Explain the NLP Processing
Layers.

Definition
Natural Language Processing (NLP) is a branch of Artificial Intelligence (AI) that enables computers to
understand, analyze, process, and generate human language such as English.

NLP Processing Layers

Input Text
↓
Acoustic / Graphemic
↓
Morphological
↓
Lexical / POS
↓
Syntactic
↓
Semantic
↓
Discourse
↓
Pragmatic

Step 1: Acoustic / Graphemic Level

● Processes speech sounds or text characters.
● Converts speech into text.

Step 2: Morphological Level

● Studies the structure of words.
● Finds root words, prefixes, and suffixes.
Example: Running → Run + ing

Step 3: Lexical / POS Level

● Splits text into words (tokens).
● Assigns Parts of Speech (POS).
Example: Dog → Noun, Run → Verb

Step 4: Syntactic Level

● Checks grammar.
● Builds sentence structure (Parse Tree).

Step 5: Semantic Level

● Finds the meaning of the sentence.
● Resolves word meanings.
Example: Bank → River bank / Financial bank

Step 6: Discourse Level

[Link]. Data Science — Natural Language Processing Page 2

 ● Connects information across sentences.
● Resolves pronouns.

Step 7: Pragmatic Level

● Understands the speaker's intention using context.
Example: "It's cold here." → Means "Please close the window."

Applications
● Machine Translation
● Chatbots
● Speech Recognition
● Sentiment Analysis
Conclusion: NLP processes language through layered stages — from raw text/speech to meaning
and intention — enabling machines to interact naturally with humans.

[Link]. Data Science — Natural Language Processing Page 3

 Q2. Differentiate between Syntactic Ambiguity and Semantic Ambiguity with
Examples.

Definition
Ambiguity means a sentence has more than one possible meaning.

1. Syntactic Ambiguity
● Caused by different sentence structures.
● Same words but different grammatical interpretation.
Example: "I saw the man with a telescope."
Meaning 1: I used a telescope.
Meaning 2: The man had a telescope.

2. Semantic Ambiguity
● Caused by words having multiple meanings.
● Sentence structure remains the same.
Example: "He went to the bank."
Meaning 1: Financial bank
Meaning 2: River bank

Difference
Syntactic Ambiguity Semantic Ambiguity

Due to sentence structure Due to word meaning

Multiple parse trees Single parse tree

Grammar causes confusion Word meaning causes confusion

Conclusion: NLP resolves ambiguity using parsing, context, and semantic analysis.

[Link]. Data Science — Natural Language Processing Page 4

 Q3. Explain the Text Preprocessing Pipeline with Example.

Definition
Text preprocessing converts raw text into clean text before analysis.
Example Input: "OMG!! It's finally happening... AI domains r scaling up!!"

Step 1: Tokenization — Split text into words

OMG | It's | finally | happening | AI | domains | r | scaling | up

Step 2: Case Folding — Convert to lowercase

omg | it's | finally | ...

Step 3: Remove Punctuation

omg | its | finally | happening | ai | domains | r | scaling | up

Step 4: Text Normalization

● r → are
● AI → Artificial Intelligence

Step 5: Stopword Removal — Remove common words

the | is | are | of | and

Step 6: Stemming / Lemmatization

● Running → Run
● Studies → Study

Step 7: Feature Representation

Convert text into numerical form using:
● Bag of Words (BoW)
● TF-IDF

Risk of Over-Preprocessing
● Important information may be lost.
● Sentence meaning may change.

Applications
● Spam Detection
● Sentiment Analysis
● Text Classification
Conclusion: A well-designed preprocessing pipeline cleans raw text while preserving meaning for
downstream NLP tasks.

[Link]. Data Science — Natural Language Processing Page 5

 Q4. Explain Stemming and Lemmatization. Which is Better for Legal
Information Retrieval?

Definition
Both techniques reduce words to their base form.

Stemming
● Removes prefixes/suffixes using simple rules.
● Faster but less accurate.

Word Stem

Researchers Research

Presenting Present

Developments Develop

Accelerating Acceler

Lemmatization
● Uses dictionary and grammar.
● Produces meaningful root words.
● More accurate.

Word Lemma

Researchers Researcher

Presenting Present

Developments Development

Accelerating Accelerate

Difference
Stemming Lemmatization

Rule-based Dictionary-based

Faster More accurate

May produce invalid words Produces valid words

Which is Better for Legal Information Retrieval?

Lemmatization is better because it:
● Gives meaningful dictionary words.
● Maintains correct legal terms.
● Improves search accuracy.
● Reduces ambiguity.
Conclusion: Stemming suits fast processing, while lemmatization is preferred where accuracy is
critical, such as legal and medical applications.

[Link]. Data Science — Natural Language Processing Page 6

 Q5. Write Regular Expressions (Regex) for the Following Patterns.

Definition
A Regular Expression (Regex) is a pattern used to search, match, and extract text.

1. Email Address
[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}

Example: abc@[Link]

2. Phone Number
(\+\d{1,3})?\d{10}

Example: +919876543210

3. Timestamp
\d{4}-\d{2}-\d{2}

Example: 2026-06-30

4. Hashtag
#\w+

Example: #AI #MachineLearning

Applications of Regex
● Email validation
● Phone number extraction
● Date and time matching
● Data cleaning
● Web scraping
● Log analysis
Conclusion: Regex is a powerful tool for extracting and validating text patterns efficiently.

[Link]. Data Science — Natural Language Processing Page 7

 PART 2 — Questions 6–10

Q6. Explain Minimum Edit Distance (MED) using Dynamic Programming.

Definition
Minimum Edit Distance (MED) is the minimum number of operations required to convert one word into
another.

Allowed Operations
● Insertion — Add a character
● Deletion — Remove a character
● Substitution — Replace one character with another
(Usually each operation has a cost of 1.)

Example: Convert slat → clots

Step 1: Draw the DP Table

Ø c l o t s

Ø 0 1 2 3 4 5

s 1

l 2

a 3

t 4

Fill the table using Dynamic Programming and find the minimum cost in the last cell.

Step 2: Edit Operations

● Substitute s → c
● Keep l
● Substitute a → o
● Keep t
● Insert s
Minimum Edit Distance = 3 (substitution cost = 1)

Applications
● Spell Checking
● Auto Correction
● DNA Sequence Matching
● Machine Translation
Conclusion: MED finds the shortest sequence of edits needed to transform one word into another.

[Link]. Data Science — Natural Language Processing Page 8

 Q7. Explain Bigram Language Model and Maximum Likelihood Estimation
(MLE).

Definition
A Bigram Language Model predicts a word based on the previous word.

Formula
P(w_i | w_(i-1)) = Count(w_(i-1), w_i) / Count(w_(i-1))

Given Corpus
neural networks learn
language models generalize
models learn structural patterns

Step 1: Count Bigrams

Bigram Count

(<s>, neural) 1

(<s>, language) 1

(language, models) 1

(models, learn) 1

Step 2: Calculate Probability

P(models | language) = 1 / 1 = 1

Similarly, calculate all required probabilities.

Advantages
● Simple to implement
● Fast computation
● Better than Unigram Model

Limitations
● Needs large corpus
● Cannot handle unseen word pairs
Conclusion: Bigram Language Models estimate sentence probability using the previous word.

[Link]. Data Science — Natural Language Processing Page 9

 Q8. Explain Add-One (Laplace) Smoothing with Example.

Definition
Add-One (Laplace) Smoothing assigns a small probability to unseen word pairs so that no probability
becomes zero.

Formula
P(w_i | w_(i-1)) = [Count(w_(i-1), w_i) + 1] / [Count(w_(i-1)) + V] (V = Vocabulary Size)

Steps
● Count bigrams.
● Add 1 to every bigram count.
● Add vocabulary size to the denominator.

Example
Count(language, models) = 1 | Count(language) = 1 | Vocabulary = 10
P(models | language) = (1+1) / (1+10) = 2/11

Why Smoothing is Needed?

Without Smoothing With Laplace Smoothing

Unseen Bigram → P = 0 P > 0 for all bigrams

Sentence Probability = 0 Every sentence gets a valid probability

Advantages
● Removes zero probability
● Handles unseen words
● Improves language model performance
Conclusion: Laplace Smoothing makes language models more reliable by assigning non-zero
probabilities to unseen word pairs.

[Link]. Data Science — Natural Language Processing Page 10

 Q9. Explain Morphological Analysis with Suitable Examples.

Definition
Morphological Analysis studies the internal structure of words by identifying their root word, prefix, and
suffix.

Types of Morphemes
● Root — Main meaning of the word.
● Prefix — Added before the root.
● Suffix — Added after the root.

Examples
Word Root Prefix Suffix Type

Irresponsible Responsible ir- — Derivational

Engineered Engineer — -ed Inflectional

-er: Deriv.
Programmers Program — -er, -s
-s: Infl.

Types of Morphology
1. Inflectional Morphology — Changes grammatical form but not meaning.
● Play → Played
● Book → Books
2. Derivational Morphology — Creates a new word or changes word class.
● Happy → Unhappy
● Teach → Teacher

Applications
● Spell Checking
● Search Engines
● Machine Translation
● Information Retrieval
Conclusion: Morphological analysis helps NLP systems understand how words are formed and
improves language processing.

[Link]. Data Science — Natural Language Processing Page 11

 Q10. Explain Hidden Markov Model (HMM) for POS Tagging.

Definition
A Hidden Markov Model (HMM) is a statistical model used to assign the most likely Part of Speech
(POS) tag to each word in a sentence.
Example Sentence: "He will project the image."
The word "project" can be Noun or Verb. HMM chooses the correct tag using probabilities.

Components of HMM
● 1. States — POS Tags (Noun, Verb, Pronoun)
● 2. Observations — Words in the sentence (He, will, project, image)
● 3. Transition Probability — Probability of moving from one POS tag to another (e.g. Pronoun
→ Verb)
● 4. Emission Probability — Probability that a word belongs to a particular POS tag, e.g.
P(project | Verb)
If P(project|Verb) > P(project|Noun), then 'project' is tagged as a Verb.

Working of HMM
Sentence
↓
Find Transition Probabilities
↓
Find Emission Probabilities
↓
Choose Most Probable POS Tags
↓
Output Tagged Sentence

Advantages
● Efficient POS tagging
● Handles ambiguity
● Uses probability for better accuracy

Applications
● POS Tagging
● Speech Recognition
● Machine Translation
● Named Entity Recognition (NER)
Conclusion: HMM combines transition and emission probabilities to predict the most probable
sequence of POS tags in a sentence.

[Link]. Data Science — Natural Language Processing Page 12

 PART 3 — Questions 11–15

Q11. Explain the Viterbi Algorithm used in HMM for POS Tagging.

Definition
The Viterbi Algorithm is a dynamic programming algorithm used in HMM to find the most probable
sequence of POS tags for a given sentence.
Example Sentence: "He will project the image." — the word "project" can be a Noun or a Verb.

Working Steps
● Step 1: Start with the first word.
● Step 2: Calculate Transition Probability (e.g. Pronoun → Verb, Verb → Noun).
● Step 3: Calculate Emission Probability (e.g. P(project|Verb), P(project|Noun)).
● Step 4: Multiply transition and emission probabilities.
● Step 5: Choose the path with the highest probability.

Flow Diagram
Sentence
↓
Transition Probability
↓
Emission Probability
↓
Calculate Path Probability
↓
Select Highest Probability Path
↓
Final POS Tags

Advantages
● Finds the best tag sequence.
● Efficient using Dynamic Programming.
● Reduces computation time.

Applications
● POS Tagging
● Speech Recognition
● Machine Translation
Conclusion: The Viterbi algorithm selects the most likely POS tag sequence by combining transition
and emission probabilities.

[Link]. Data Science — Natural Language Processing Page 13

 Q12. Differentiate between Finite State Automata (FSA) and Finite State
Transducer (FST).

Definition
FSA is a machine that accepts or rejects input strings. FST is a machine that accepts input and
produces an output.

Differences
FSA FST

Accepts or rejects strings Converts input into output

Only input symbols Input and output symbols

Used for pattern matching Used for word transformation

No output generation Generates output

Example
FSA — Input: "cats" → Accepts (follows valid pattern).
FST — Input: "wolves" → Output: "wolf"

Applications
FSA FST

Spell Checking Morphological Analysis

Pattern Matching Machine Translation

Token Recognition Speech Processing

Conclusion: FSA recognizes valid strings, whereas FST transforms one form into another.

[Link]. Data Science — Natural Language Processing Page 14

 Q13. Design an FSA and FST for English Plural Words.

(A) Finite State Automata (FSA)

The FSA accepts plural words ending with -s, -es, and -ies.
Start
↓
Root Word
■■■■ s ■■■■ Accept
■■■■ es ■■■ Accept
■■■■ ies ■■ Accept

Root Word Plural Form

Book Books ✔

Match Matches ✔

Factory Factories ✔

(B) Finite State Transducer (FST)

The FST converts plural words into singular words.

Input Output

Wolves Wolf

Matches Match

Factories Factory

Working
Input Word
↓
Identify Plural Ending
↓
Remove Ending
↓
Generate Singular Form

Applications
● Morphological Analysis
● Spell Checking
● Search Engines
● Machine Translation
Conclusion: FSA recognizes plural words, while FST converts them into their root forms.

[Link]. Data Science — Natural Language Processing Page 15

 Q14. Explain Context-Free Grammar (CFG) and Leftmost Derivation.

Definition
A Context-Free Grammar (CFG) is a set of production rules used to describe the grammatical structure
of sentences.
Example Sentence: "A professor teaches the class."

Grammar Rules
S → NP VP
NP → Det N
VP → V NP
Det → A | the
N → professor | class
V → teaches

Leftmost Derivation
S
⇒ NP VP
⇒ Det N VP
⇒ A professor VP
⇒ A professor V NP
⇒ A professor teaches NP
⇒ A professor teaches Det N
⇒ A professor teaches the class

Components of CFG
● Non-Terminals (S, NP, VP)
● Terminals (A, professor, teaches, class)
● Production Rules
● Start Symbol (S)

Applications
● Syntax Checking
● Compiler Design
● NLP Parsing
● Grammar Checking
Conclusion: CFG represents sentence structure using production rules, while leftmost derivation
generates the sentence step by step.

[Link]. Data Science — Natural Language Processing Page 16

 Q15. Draw the Parse Tree for the Sentence "A professor teaches the class".

Definition
A Parse Tree is a hierarchical tree that represents the grammatical structure of a sentence.
Sentence: "A professor teaches the class."

Parse Tree
S
/ \
NP VP
/ \ / \
Det N V NP
| | | / \
A professor teaches Det N
| |
the class

Explanation
● Subject (Noun Phrase - NP): A, Professor
● Predicate (Verb Phrase - VP): Teaches, The class

Advantages
● Shows grammatical structure.
● Identifies subject and predicate.
● Helps detect syntax errors.
● Used in machine translation and question answering.

Applications
● Syntax Analysis
● Grammar Checking
● Machine Translation
● Speech Processing
Conclusion: The parse tree clearly separates the Subject (NP) and Predicate (VP), helping NLP
systems understand sentence structure.

[Link]. Data Science — Natural Language Processing Page 17

 PART 4 — Questions 16–20

Q16. Explain the CYK Algorithm and Probabilistic CFG (PCFG).

Definition
The Cocke–Younger–Kasami (CYK) Algorithm is a dynamic programming algorithm used to check
whether a sentence can be generated by a Context-Free Grammar (CFG). A Probabilistic Context-Free
Grammar (PCFG) assigns probabilities to grammar rules to select the most likely parse tree.

Why is CYK Needed?

Normal top-down and bottom-up parsers take more time for ambiguous sentences and may generate
many unnecessary parse trees. CYK solves this using:
● Dynamic Programming
● Storing intermediate results
● Avoiding repeated calculations

Steps of CYK
● Step 1: Convert CFG into Chomsky Normal Form (CNF).
● Step 2: Fill the table with grammar rules.
● Step 3: Combine smaller parts to form larger phrases.
● Step 4: Check whether the start symbol S appears in the final cell.

CYK Flow
Input Sentence
↓
Convert CFG to CNF
↓
Fill DP Table
↓
Combine Grammar Rules
↓
Sentence Accepted or Rejected

Probabilistic CFG (PCFG)

Assigns probability to each grammar rule and chooses the parse tree with the highest probability.
S → NP VP (0.9) | S → VP (0.1)

Advantages
● Faster parsing.
● Handles ambiguity.
● Finds the most probable parse tree.

Applications
● Machine Translation
● Grammar Checking
● Speech Recognition

[Link]. Data Science — Natural Language Processing Page 18

 Conclusion: CYK efficiently parses sentences, while PCFG helps choose the best parse tree using
probabilities.

[Link]. Data Science — Natural Language Processing Page 19

 Q17. Explain Semantic Role Labeling (SRL) with Example. Compare SRL
with POS Tagging.

Definition
Semantic Role Labeling (SRL) identifies the role played by each word or phrase in a sentence.
Example Sentence: "The technician repaired a server for the client inside the datacenter."

Semantic Roles
Word / Phrase Role

Technician Agent (Performs action)

Repaired Predicate (Action)

Server Patient (Receives action)

Client Beneficiary

Datacenter Locative (Place)

SRL Diagram
Agent → Predicate → Patient
Technician → Repaired → Server
↓
Beneficiary: Client
↓
Locative: Datacenter

SRL vs POS Tagging

SRL POS Tagging

Finds semantic roles Finds grammatical category

Focuses on meaning Focuses on grammar

Agent, Patient, Location Noun, Verb, Adjective

Applications
● Question Answering
● Information Extraction
● Machine Translation
● Chatbots
Conclusion: SRL explains who did what, to whom, where, and why, while POS tagging only
identifies grammatical categories.

[Link]. Data Science — Natural Language Processing Page 20

 Q18. Explain Word Sense Disambiguation (WSD) using the Lesk Algorithm.

Definition
Word Sense Disambiguation (WSD) is the process of identifying the correct meaning of a word based
on its context.
Sentence 1: "The battery has a weak charge." → Meaning: Electrical charge
Sentence 2: "The officer will charge the suspect." → Meaning: Accuse legally

Lesk Algorithm
The Lesk Algorithm compares the dictionary definitions of different meanings with the surrounding
context words. The meaning with the maximum word overlap is selected.

Steps
● Step 1: Identify the ambiguous word.
● Step 2: Find all meanings from the dictionary.
● Step 3: Compare each meaning with the sentence.
● Step 4: Select the meaning with the highest overlap.

WordNet-Based Similarity
● Uses WordNet relationships.
● Measures similarity between words.
● More accurate than simple dictionary matching.

Comparison
Lesk Algorithm WordNet Similarity

Dictionary-based WordNet-based

Uses word overlap Uses semantic relationships

Simple More accurate

Applications
● Machine Translation
● Search Engines
● Chatbots
● Question Answering
Conclusion: WSD helps NLP systems understand the correct meaning of ambiguous words using
context.

[Link]. Data Science — Natural Language Processing Page 21

 Q19. Explain WordNet and Lexical Relations with Examples.

Definition
WordNet is a lexical database that groups words with similar meanings into Synsets and shows
relationships between words.

Lexical Relations
● 1. Word Sense — Different meanings of a word. Example: Bank (Financial bank / River bank)
● 2. Synset — A group of words with the same meaning. Example: Big = Large = Huge
● 3. Synonymy — Words with similar meanings. Example: Happy → Joyful
● 4. Antonymy — Words with opposite meanings. Example: Hot ↔ Cold
● 5. Hypernymy — General category. Example: Animal → Dog
● 6. Hyponymy — Specific category. Example: Dog → Labrador

Diagram
Animal
↓
Dog
↓
Labrador

Applications
● Search Engines
● Machine Translation
● Information Retrieval
● Word Sense Disambiguation
Conclusion: WordNet helps NLP systems understand word meanings and semantic relationships.

[Link]. Data Science — Natural Language Processing Page 22

 Q20. Explain the NLTK Pipeline for Text Classification or Named Entity
Recognition (NER).

Definition
NLTK (Natural Language Toolkit) is a Python library used for Natural Language Processing tasks.

NLTK Pipeline for Text Classification

● Step 1: Tokenization — Split text into words.
● Step 2: Text Preprocessing — Lowercase conversion, remove punctuation, remove
stopwords, stemming/lemmatization.
● Step 3: Feature Extraction — Convert text into numerical features (Bag of Words, TF-IDF).
● Step 4: Train the Model — Train a classifier using labeled data (e.g. Naïve Bayes, Decision
Tree).
● Step 5: Evaluate — Measure performance using Accuracy, Precision, Recall, F1-score.

Pipeline Diagram
Input Text
↓
Tokenization
↓
Preprocessing
↓
Feature Extraction
↓
Train Classifier
↓
Prediction & Evaluation

NER Pipeline (Alternative)

Sentence
↓
Tokenization
↓
POS Tagging
↓
Chunking
↓
Named Entity Recognition

Example: "John works at Google in Bengaluru."

John → Person | Google → Organization | Bengaluru → Location

Applications
● Spam Detection
● Sentiment Analysis
● Chatbots
● Information Extraction
● Search Engines
Conclusion: NLTK provides an easy and efficient pipeline for building NLP applications such as Text
Classification and Named Entity Recognition (NER).

[Link]. Data Science — Natural Language Processing Page 23