Part A — 1 Mark Questions (Q1–Q39)
1. De ne tokenization with example.
Tokenization is splitting text into smaller units (tokens) such as words or sentences.
Example: "I like NLP" → ["I", "like", "NLP"].
2. What does phonology describe regarding words?
Phonology describes the sound system of a language, including how sounds (phonemes) function
and combine in words.
3. How irregularity of words can be handled?
By using lemmatization, morphological rules, and exception dictionaries to handle irregular forms
(e.g., go → went).
4. Stem and af x of “studies” using morphology.
Stem: study, Af x: -es.
5. Five applications of NLP.
Machine translation, sentiment analysis, speech recognition, text summarization, question
answering.
6. Simplest form of syntactic analysis mentioned.
Shallow parsing (chunking).
7. Dependency graph vs phrase structure tree.
Dependency graph shows relationships between words; phrase structure tree shows hierarchical
phrase composition.
8. Jaccard distance for 'GOOD' and 'GOOGLE' (n=2).
GOOD bigrams: GO, OO, OD
GOOGLE bigrams: GO, OO, OG, GL, LE
Intersection= {GO, OO} → size 2; Union=6; Distance = 1 − 2/6 = 0.6667.
9. Differentiate Constituency and Dependency trees.
Constituency: phrase-based hierarchy; Dependency: word-to-word relations. Example: “She eats
apples” → Dependency connects “eats” to “She” and “apples”.
10. Example using Minimum Spanning Tree.
In dependency parsing, MST algorithm selects dependency edges with maximum scores to form a
tree connecting all words.
11. Primary goal of NLP.
To enable computers to understand, interpret, and generate human language.
12. Word changes from singular to plural.
This is in ection—changing word form to indicate number, tense, etc.
13. Agglutinative vs fusional languages.
Agglutinative: one morpheme = one meaning; Fusional: one morpheme = multiple meanings.
fi
fl
fi
fi
14. Main issues in word structure.
Irregular forms, compounding, in ection, derivation, ambiguity.
15. Why use homonyms with examples.
Homonyms enrich language but cause ambiguity. Example: bat (animal / sports), bank (river /
nance).
16. Purpose of treebank.
A treebank is a corpus with syntactic annotations used to train parsers.
17. Purpose of parsing.
To determine syntactic structure, aiding in meaning extraction.
18. Find Jaccard distance for 'BOOK' and 'SHOOT' (n=2).
BOOK: BO, OO, OK
SHOOT: SH, HO, OO, OT
Intersection={OO} (size=1); Union=6; Distance=1−1/6=0.8333.
19. (Duplicate of 18; same answer) 0.8333.
20. Dependency tree for "John saw Mary".
saw is root; John → subject; Mary → object.
21. (Duplicate of Q10) MST example: selecting highest-probability dependency edges to connect
all words.
22. (Duplicate of Q11) Primary goal: enable machines to process human language.
23. (Duplicate of Q12) In ection.
24. (Duplicate of Q13) Agglutinative vs fusional difference.
25. (Duplicate of Q14) Word structure issues.
26. (Duplicate of Q15) Homonyms with examples.
27. (Duplicate of Q16) Treebank purpose.
28. (Duplicate of Q17) Parsing purpose.
29. (Duplicate of Q18) Jaccard distance for BOOK & SHOOT: 0.8333.
30. (Duplicate of Q20) Dependency tree.
31. Operations in Shift Reduce Parsing.
Shift, Reduce, Accept, Error.
32. Two examples of personal assistants using speech recognition.
Siri, Google Assistant.
33. Plural of “mouse” to “mice” process.
This is irregular morphological in ection (internal vowel change).
fi
fl
fl
fl
34. Role of lemma in linguistics.
Lemma is the base dictionary form; helps normalize words for analysis.
35. Stem and af x of “International”.
Stem: nation, Af xes: inter- (pre x), -al (suf x).
36. Syntax vs semantics.
Syntax = sentence structure; Semantics = meaning.
37. Two main syntax analysis approaches in treebanks.
Constituency parsing, Dependency parsing.
38. Parsing algorithm with stack & buffer.
Shift–Reduce parsing.
39. CKY algorithm achieves…
It performs ef cient bottom-up parsing for CFGs in Chomsky Normal Form.
fi
fi
fi
fi
fi
Part B — 5 Mark Questions (Q1–Q18)
Q1 — Finite State Morphology (with example)
De nition (short):
Finite-State Morphology models morphological analysis/generation using nite-state machines —
typically nite-state transducers (FSTs) — that map between lexical representations (morphemes
+ tags) and surface word forms.
How it works (intuitively):
• The FST reads a lexical form like cat +PL and outputs cats.
• Transitions correspond to reading letters/morpheme boundaries and emitting output letters;
special transitions apply morphological rules (e.g., add s, change y→ies).
Example (English plural rule):
• Lexical input: baby +PL
• Using an FST: baby +PL → detect nal y preceded by consonant → output bab + ies
→ babies.
• FST states: read root (b→a→b→y), on +PL branch rule for y→ies.
Why useful: Fast, composable, and can model both regular and many irregular processes
(exceptions via lexicon).
Q2 — Types of sequence classi cation methods (overview)
Broad families:
1. Feature-based / classical: Bag-of-words, TF-IDF, n-gram models → + classi ers (SVM,
logistic regression).
2. Sequence probabilistic models: Hidden Markov Models (HMMs), Conditional Random
Fields (CRFs) (CRFs usually for labeling, can be adapted).
3. Kernel methods: SVM with string/sequence kernels (subsequence or spectrum kernels).
4. Neural methods: RNNs, LSTMs, GRUs (handle order & variable length).
5. Convolutional models: 1D CNNs for local patterns (n-gram style features).
6. Transformers / Self-attention: BERT, RoBERTa, GPT — state of the art for many
sequence tasks.
7. Embedding + classi er: Sentence embeddings (Doc2Vec, Sentence-BERT) → MLP /
SVM.
fi
fi
fi
fi
fi
fi
fi
When to choose: simple BoW for small data or interpretability; RNN/CNN for sequence
dependencies; Transformers when long-range context & top accuracy matter.
Q3 — Sentence boundary (illustration + boundaries for the
given example)
Sentence boundary (de nition): the location where one sentence ends and the next begins —
typically marked by ., ?, !possibly with trailing quotes or parentheses.
Dif culties: abbreviations (Dr.), quotes, ellipses, multi-line text.
Given text (rewritten as single line):
“Dr. Smith said, 'The patient is recovering well.' The nurse
nodded in agreement.”
Boundaries (two sentences):
1. Dr. Smith said, 'The patient is recovering well.'
2. The nurse nodded in agreement.
Why: Dr. contains a period but is an abbreviation (not an end-of-sentence). The quoted clause
ends with . inside quotes — that marks the rst sentence end; the next sentence begins after the
closing quote/space.
Q4 — Shift-Reduce parsing for grammar
Grammar:
less
CopyEdit
S → ( L ) | a
L → L , S | S
Input: ( a , ( a , a ) ) (I’ll show steps; $ is end marker)
We show stack / input / action:
ruby
CopyEdit
Stack Input Action
-------------------------------------------------------------
-
[] ( a , ( a , a ) ) $ start
[(] a , ( a , a ) ) $ shift
'('
fi
fi
fi
[(, a] , ( a , a ) ) $ shift
'a'
[(, S] , ( a , a ) ) $ reduce S
→ a
[(, S, ,] ( a , a ) ) $ shift
','
[(, S, ,, (] a , a ) ) $ shift
'('
[(, S, ,, (, a] , a ) ) $ shift
'a'
[(, S, ,, (, S] , a ) ) $ reduce S
→ a
[(, S, ,, (, S, ,] a ) ) $ shift
','
[(, S, ,, (, S, ,, a] ) ) $ shift
'a'
[(, S, ,, (, S, ,, S] ) ) $ reduce S
→ a
[(, S, ,, (, S, ,, )] ) $ shift
')'
[(, S, ,, (, S, )] ) $ reduce S
→ (L)
[(, S, ,, L] ) $ reduce L
→ L , S (where L was S)
[(, S, ,, L] ) $ now we
have ( S , L ) structure
[(, S, ,, L, )] $ shift
')'
[(, S, L ] $ reduce S
→ (L)
[(, S ] $ reduce L
→ L , S (to combine earlier)
[ S ] $ reduce S
→ (L) or final reductions
[ S ] $ ACCEPT
(Above is a conceptual trace — reductions L → L , S combine the a and (a,a) into the list L
inside the outer parentheses; then S → (L) reduces (a,(a,a)) to S, and outer parentheses
produce the full parse.)
Result: Input parsed successfully. A parse tree is formed where outer S → (L) and L contains
two S nodes: a and (a,a).
Q5 — Distances: "thermodynamics" vs
"hydrodynamics"
We compute (a) Jaccard distance for trigrams (n = 3), and (b) Levenshtein (edit) distance with
operations (insertion, deletion, substitution) cost = 1.
(a) 3-grams (trigrams):
thermodynamics trigrams (contiguous):
the, her, erm, rmo, mod, ody, dyn, yna, nam, ami, mic, ics →
12 distinct trigrams.
hydrodynamics trigrams:
hyd, ydr, dro, rod, ody, dyn, yna, nam, ami, mic, ics → 11 distinct
trigrams.
• Intersection (common trigrams): {ody, dyn, yna, nam, ami, mic, ics}
→ 7 items.
• Union size = 12 + 11 − 7 = 16.
Jaccard similarity = 7 / 16 = 0.4375
Jaccard distance = 1 − 0.4375 = 0.5625
(b) Edit (Levenshtein) distance (ops: insertion, deletion, substitution cost =1):
Compute minimal edit distance between the two words → 4.
One minimal sequence of edits (transform thermodynamics → hydrodynamics):
1. Delete 't' at position 1.
2. Substitute 'e' → 'y' (position 3 in original).
3. Insert 'd' at the correct position (to produce hydro pre x).
4. Delete 'm' (to adjust thermo→hydro alignment).
So Levenshtein distance = 4 (with operations as above).
Q6 — Ambiguity of grammar
Grammar:
bash
CopyEdit
S → S * S
S → S - S
S → id
String: id * id - id
Claim: Grammar is ambiguous.
fi
Reason: The string id * id - id has at least two different parse trees (two different
groupings):
1. (id * id) - id
Parse: S → S - S with left S → S * S → id * id.
2. id * (id - id)
Parse: S → S * S with right S → S - S → id - id.
Two different parse trees for the same terminal string ambiguous.
Q7 — Different phases of NLP (with an example pipeline)
Typical NLP pipeline phases:
1. Text Collection / Input (raw text, speech-to-text)
2. Text Normalization / Cleaning (lowercasing, whitespace, remove noise)
3. Tokenization (split into tokens/words/sentences)
4. Morphological Analysis (stemming, lemmatization, POS tags)
5. Syntactic Analysis / Parsing (constituency/dependency parsing)
6. Semantic Analysis (named entities, word sense, semantic roles)
7. Discourse / Pragmatics (coreference resolution, dialogue state)
8. Application-speci c tasks (summarization, translation, sentiment, QA)
Example (processing a sentence):
Input: "Dr. Smith said he's fine."
• Tokenize → ["Dr.", "Smith", "said", "he", "'s", "fine",
"."]
• POS tagging → Dr./NNP, Smith/NNP, said/VBD...
• Parse → produce dependency tree
• Semantic → entity recognition (Dr. Smith PERSON)
• Output → answer query, summarize, etc.
Q8 — Functional Morphology (with example)
fi
Functional morphology refers to the study of what morphological changes do — the
grammatical functions encoded by morphemes (number, tense, case, person, aspect, etc.) and how
morphological forms realize those functions.
Example:
• English plural -s indicates number = plural (function).
dog (singular) → dog + PL → dogs.
• Past tense -ed marks tense = past (function).
walk → walked.
Derivational vs in ectional (functional contrast):
• In ectional morphology modi es form for grammatical functions (tense, number) but
doesn’t change category: run → runs (verb → verb).
• Derivational morphology creates new words and can change category: happy →
unhappy (adjective) or happy → happiness (noun) — functions: produce antonymy
/ nominalization.
Q9 — Stemming vs Lemmatization (compare + two examples)
Stemming: crude stripping of af xes to reduce a token to a base form (not necessarily a real word).
Fast, rule-based (Porter, Snowball).
Lemmatization: uses vocabulary and morphological analysis to return dictionary/lemma form (real
word), often uses POS.
Key differences:
• Stemmers can produce non-words (running → run or runn depending on stemmer).
• Lemmatizer returns valid base form (running → run), but requires POS/context.
Examples:
1. Word: better
◦ Stemmer output (Porter): better (may not change)
◦ Lemmatizer (with POS=adj): good (lemma)
2. Word: studies
◦ Stemmer: studi (or studi with Porter)
◦ Lemmatizer (with POS=verb): study
fl
fl
fi
fi
Q10 — Distances: "principal" vs "principle"
Compute (a) Jaccard with n=3 (trigrams) and (b) edit distance.
(a) 3-grams:
principal trigrams: pri, rin, inc, nci, cip, ipa, pal (list depends on
string; ensure exact) — let’s show distinct trigrams: {pri, rin, inc, nci, cip,
ipa, pal} → 7 items.
principle trigrams: pri, rin, inc, nci, cip, ipl, ple → {pri, rin,
inc, nci, cip, ipl, ple} → 7 items.
• Intersection = {pri, rin, inc, nci, cip} → 5 items.
• Union size = 7 + 7 − 5 = 9.
Jaccard similarity = 5 / 9 ≈ 0.5556
Jaccard distance = 1 − 5/9 = 4/9 ≈ 0.4444
(b) Edit distance (Levenshtein):
Minimum edits transforming principal → principle = 2.
One minimal sequence:
1. Delete 'a' (the 'a' in principal near end).
2. Insert 'e' at the end (to get principle).
So distance = 2 (insertion + deletion) with unit cost operations.
Q11 — CFG membership by shift-reduce (grammar & string)
Grammar:
css
CopyEdit
S → S A
A → A A
S → b
A → a
Input string: b a a a a (i.e., baaaa)
Goal: show shift–reduce parsing (bottom-up) that yields S.
Trace (stack | remaining | action):
ruby
CopyEdit
[] b a a a a $ start
[b] a a a a $ shift 'b'
[S] a a a a $ reduce S → b
[S a] a a a $ shift 'a'
[S A] a a a $ reduce A → a
[S A a] a a $ shift 'a'
[S A A] a a $ reduce A → a
[S A A a] a $ shift 'a'
[S A A A] a $ reduce A → a
[S A A A a] $ shift 'a'
[S A A A A] $ reduce A → a
[S A A A] $ reduce S → S A
[S A] $ reduce S → S A
[S] $ reduce S → S A
[S] $ ACCEPT
Explanation: After converting each a to A via A → a, we have S A A A A. Repeatedly reduce
S A → S using S → S Auntil only S remains. Thus baaaa ∈ L(G).
Q12 — Constituency-based parsing (clari cation requested)
The le’s Q12 looks truncated: it asks “De ne Constituency -based Parsing. Draw Constituency
-based Parsing tree for the sentence " How” — I think the sentence to tree is incomplete.
Please con rm the exact sentence you want a constituency tree for (examples: "How are
you?", "How did John leave?", etc.). I’ll produce the tree immediately after you
con rm.
Q13 — Determine performance of approaches in structure of
documents
Interpretation & answer (general):
Performance of document-structure approaches (e.g., segmentation, parsing, summarization) is
typically evaluated using task-speci c metrics:
• Segmentation/topic boundary detection: Pk, WindowDiff, precision/recall on boundary
detection.
• Parsing / tree structure: labeled/unlabeled attachment score (LAS/UAS) for dependency
parsing; parseval (precision/recall on constituents) for constituency parsing.
• Information extraction / structure extraction: precision, recall, F1 for extracted elds.
• Summarization (structure-preserving): ROUGE variants measure overlap with reference
summaries.
• Overall system evaluation: human judgments (readability, coherence), confusion matrix,
accuracy.
fi
fi
fi
fi
fi
fi
fi
Takeaway: choose metrics aligned with the structural property you evaluate (boundaries, tree
edges, extracted elements).
Q14 — Uni cation-based morphology (with example)
What it is:
Uni cation morphology uses feature structures (attribute-value matrices — AVMs) to represent
morphemes and combines them by uni cation (merging compatible feature structures). It is
common in uni cation grammars (HPSG, LFG) and for morphologically rich languages.
Example (English noun phrase agreement):
Two feature structures:
• Noun dogs: [CAT: noun, NUMBER: plural]
• Determiner the: [CAT: det, NUMBER: plural] (when agreeing)
Unify determiner and noun for agreement: both have NUMBER: plural → uni cation
succeeds.
Morphological example: verb lemma walk with features [VFORM: base] + past tense
morpheme -ed as rule requiring [TENSE: past] → uni cation yields walked with
[TENSE: past].
Uni cation allows constraints (e.g., case, number, person) to propagate across constituents.
Q15 — Topic boundary detection methods (illustrate)
Goal: nd boundaries between topics/segments in a document.
Common methods:
1. TextTiling (Hearst): sliding windows compare lexical similarity (cosine) between adjacent
blocks; peaks signal boundaries.
2. Lexical Cohesion / Word Distribution: compute similarity of vocabulary distribution
across segments.
3. Bayesian Topic Models: e.g., a hierarchical Bayesian model where topic switches are latent
variables inferred from word distributions.
4. Supervised classi ers: train models using features (cue words, punctuation, similarity
scores) to predict boundary points.
5. Embedding-based methods: use sentence embeddings (BERT) and detect drops in
embedding similarity (cosine distance peaks).
6. Graph / clustering methods: cluster sentences into topical groups; edges with low weights
indicate boundaries.
fi
fi
fi
fi
fi
fi
fi
fi
fi
Evaluation: Pk, WindowDiff, precision/recall.
Q16 — Shift-Reduce parsing for grammar (we already
covered earlier)
(This was Question earlier in your rst part; if you want a fresh trace, say which grammar & input.
If you mean the grammar S -> a+a | a-a | a | (a) and input a-(a+a) — I
previously provided a complete shift–reduce trace. Tell me if you want it repeated or rendered
differently.)
Q17 — CYK algorithm for the CFG and string abbb
Grammar:
css
CopyEdit
S →
S A
A →
A A
S a→
A b→
String: a b b b (positions 1..4)
Is the string in the language? Use CYK (table for lengths 1..4):
• Length 1 (terminals):
◦ pos1 a → {S}
◦ pos2 b → {A}
◦ pos3 b → {A}
◦ pos4 b → {A}
• Length 2:
◦ span (1,2) ab: check splits (1)(2) → {S}{A} → S → S A applies → add S
◦ span (2,3) bb: {A}{A} → A → A A applies → add A
◦ span (3,4) bb: {A}{A} → A
• Length 3:
◦ span (1,3) abb: splits:
▪ (1)(2-3): {S}{A} → S → S A → add S
fi
◦ span (2,4) bbb: {A}{A A} or {A A}{A} → A → A A → add A
• Length 4 (whole string):
◦ span (1,4) abbb: split (1)(2-4): {S}{A} → S → S A → add S.
Top cell (1,4) contains S CYK accepts the string abbb. So yes, it belongs to the grammar.
(Concrete leftmost derivation: S ⇒ S A ⇒ S A A ⇒ S A A A ⇒ a A A A ⇒ a b
b b.)
Q18 — Distances: "algorithm" vs "logarithm"
(a) Jaccard distance (n = 3)
Trigrams:
• algorithm: alg, lgo, gor, ori, rit, ith, thm → 7 trigrams.
• logarithm: log, oga, gar, ari, rit, ith, thm → 7 trigrams.
Intersection: {rit, ith, thm} → size 3
Union size = 7 + 7 − 3 = 11
Jaccard similarity = 3 / 11 ≈ 0.2727
Jaccard distance = 1 − 3/11 = 8/11 ≈ 0.72727
(b) Edit (Levenshtein) distance (insert/delete/substitute cost = 1)
Minimum edit distance between algorithm and logarithm = 3.
One optimal edit sequence (convert algorithm → logarithm):
1. Substitute 'a' → 'l' (pos1)
2. Substitute 'l' → 'o' (pos2)
3. Substitute 'o' → 'a' (pos4) — after rst two subs the alignment leads to this minimal
set.
(Various sequences of 3 substitutions convert one to the other; minimal cost = 3.)
fi