IAT 1 Question Bank

CMC733 IAT-1 Question Bank — Exam-Ready Answers

Convention: Each answer is written for 10 marks. Probabilities are maximum-likelihood estimates unless stated otherwise. <s> and </s> are sentence-boundary symbols. When a question does not provide enough corpus information, the assumption used for the worked answer is stated explicitly.

Module I

1. Differentiate between lexical ambiguity and syntactic ambiguity in Natural Language Processing with suitable examples.

Answer. Lexical ambiguity occurs when one word or surface form has more than one possible sense or grammatical category. Syntactic (structural) ambiguity occurs when the same sequence of words has more than one valid grammatical structure or parse tree.

Lexical example. In The bank approved the loan, the words approved and loan strongly favour the financial sense. In The boat reached the bank, boat and reached favour the river-bank sense. The spelling bank is identical, but the lexical sense differs. Lexical ambiguity can also be a POS ambiguity: They will **book** a room (book/VB) versus The **book** is old (book/NN).

Syntactic example.

I saw [the man with a telescope].   PP attaches to man:
                                    the man possessed/was associated with it.

I saw [the man] [with a telescope]. PP attaches to saw:
                                    the telescope was the instrument.

Both structures contain the same words. A context-free grammar may license both VP -> VP PP and NP -> NP PP; a statistical parser ranks them, while world knowledge and a preceding sentence can decide the intended reading.

The two ambiguities interact. In I saw her duck, duck may be a noun (her bird) or a verb (her lowering her head), producing lexical/POS and structural differences. Therefore, an NLP pipeline generally (1) generates lexical candidates, (2) builds possible syntactic parses, and (3) ranks them with semantic, discourse, and pragmatic evidence. A probability of a word or parse is not a guarantee that its interpretation is correct. The distinction between lexical and structural ambiguity follows the standard layered treatment in Jurafsky & Martin, Ch. 2 and Ch. 18.

2. Explain the major applications of Natural Language Processing. For each application, describe the NLP task involved and give a real-world example.

Answer. NLP applications convert human language into a useful prediction, search result, structured record, translation, or generated response. A strong description gives the input, task, output, and a failure risk.

A complete system is usually a pipeline. For question answering, for example, the system may tokenize and normalize the question, detect its intent and entities, retrieve passages, rank evidence, read the relevant passage, and produce an answer with a citation. Retrieval finds evidence; generation writes language; these should not be confused. Evaluation must match the task: ranking metrics for retrieval, accuracy/F1 for classification or extraction, translation quality plus human review for translation, and factuality/coverage in addition to overlap for summaries. Sarcasm, negation, domain shift, privacy, bias, and unsupported generated claims are common failure modes. The application/task distinction is summarized in Jurafsky & Martin and the NPTEL NLP course.

3. Explain the various stages of Natural Language Processing (NLP) with a suitable example.

Answer. A traditional NLP system moves from the surface form of language toward structure, meaning, discourse, and an application output. The stages are pedagogical: modern neural systems may learn several stages jointly, but the distinctions remain useful for design and error analysis.

raw characters
      |
script/language handling -> sentence and word tokenization
      |
normalization and filtering -> morphology/lemmatization
      |
lexical analysis and POS tagging -> syntactic parsing
      |
semantic analysis -> discourse/coreference -> pragmatic interpretation
      |
translation, search, classification, QA, or generation

1. Input and script handling: Decode Unicode, identify language/script where necessary, preserve meaningful punctuation, and handle OCR/ASR noise.
2. Sentence segmentation: Find sentence boundaries using punctuation and learned rules; abbreviations such as Prof. make this non-trivial.
3. Tokenization: Split into words, punctuation, numbers, URLs, emojis, or subwords. Tokenization is task- and language-dependent.
4. Normalization/preprocessing: Apply safe case normalization, Unicode normalization, punctuation policy, stop-word policy, and noise filtering. These choices must not erase information needed by the task.
5. Morphological analysis: Identify lemma and grammatical features, e.g. emailed -> email + V + PAST; a stemmer may only produce a heuristic stem.
6. Lexical analysis/POS tagging: Assign categories such as proper noun, verb, determiner, noun, and adverb in context.
7. Syntactic analysis: Build constituents or dependencies and identify relations such as subject, object, and modifier.
8. Semantic analysis: Determine word senses, named entities, semantic roles, and a compositional meaning representation.
9. Discourse and pragmatics: Link references between sentences, identify the topic, infer speaker intention, and use situational/world knowledge.
10. Application processing: Use the representation for translation, retrieval, sentiment analysis, summarization, or dialogue.

Worked example: Riya emailed Prof. Sen yesterday.

There is error propagation: a bad token boundary can cause incorrect morphology, which can cause a wrong POS tag and parse. A modular pipeline is interpretable and replaceable; a joint model can reduce boundary errors but is harder to inspect. Jurafsky & Martin, Ch. 2 discusses words/tokens, and NLTK Chapter 3 provides practical preprocessing examples.

4. What is ambiguity in Natural Language Processing? Explain the different types of ambiguity with suitable examples.

Answer. Ambiguity is the existence of two or more distinct analyses or interpretations for the same linguistic input. It is different from vagueness: vague expressions have an imprecise range, whereas ambiguity presents competing alternatives. An NLP system should retain plausible candidates until enough evidence is available to rank them.

1. Lexical ambiguity: One word has multiple senses or categories. bank can mean a financial institution or river edge; book can be a noun or verb.
2. Morphological ambiguity: One surface form has multiple morpheme analyses or grammatical readings. unlockable can mean “not lockable” or “able to be unlocked”; studies can be plural noun or third-person-singular verb.
3. Syntactic/structural ambiguity: A sentence has multiple parse trees. I saw the boy with a telescope permits instrument and PP-attachment readings.
4. Semantic ambiguity: A structure has more than one compositional meaning, often due to word sense or quantifier scope. Every student read a book may allow one common book or potentially different books.
5. Referential/anaphoric ambiguity: A pronoun or referring expression has multiple antecedents. Ravi told Amit that he won does not determine whether he is Ravi or Amit.
6. Pragmatic ambiguity: The intended speech act depends on situation and speaker goals. Can you open the window? literally asks about ability but normally functions as a request.
7. Discourse ambiguity: The relation between clauses/sentences is underdetermined. Maya dropped the glass. It broke. requires discourse linking, and it could in principle have other candidate antecedents in a longer context.
8. Phonological/orthographic ambiguity: Speech or writing supports alternatives, as with homophones two/to/too, missing word boundaries, or noisy ASR output.

Resolution strategy. A lexical analyzer and tagger generate candidates; a parser checks grammatical structures; semantic constraints eliminate impossible combinations; a coreference system applies number, gender, syntactic and discourse constraints; a language model or classifier ranks the remaining readings; pragmatic/world knowledge handles intention and plausibility. For example, The bank approved the loan is resolved using lexical context and selectional expectations rather than the string bank alone.

Ambiguity is layered, so one sentence can exhibit several types simultaneously. Indian and other regional languages may additionally have ambiguity from rich inflection, compounding, flexible word order, script segmentation, code-mixing, and limited lexical resources; the exact pattern is language-specific. See Jurafsky & Martin, Ch. 2, Ch. 18, and Ch. 23.

5. Describe semantic analysis in Natural Language Processing. Explain its major tasks with suitable examples.

Answer. Semantic analysis maps syntactically analyzed language to an interpretation of what expressions denote, how entities and events relate, and what a sentence asserts. It deals with word meaning and compositional sentence meaning; it is not merely dictionary lookup. The meaning of a larger expression depends on its parts and their grammatical combination, while context can resolve remaining alternatives.

Typical semantic pipeline:

words/POS -> word senses and entities -> composition of phrases
          -> predicates/arguments and roles -> discourse/world constraints
          -> structured meaning used by the application

Major tasks are:

1. Word-sense disambiguation (WSD): Select the appropriate sense of a polysemous word. The fisherman sat on the bank favours the river sense; The bank approved the loan favours the financial sense. Contextual classifiers, knowledge-based methods such as Lesk, and embeddings can be used.
2. Lexical semantic relations: Represent synonymy (big/large), antonymy (hot/cold), hyponymy (rose/flower), and homonymy. These relations support search and question answering.
3. Named-entity recognition and normalization: Mark and type spans: Dr. Sen as PERSON, Pune as LOCATION, 12 August as DATE, and link aliases to a canonical entity where possible.
4. Semantic role labeling (SRL): Assign predicate-argument roles. In Riya emailed Prof. Sen, emailed is the predicate, Riya is the sender/agent, and Prof. Sen is the recipient.
5. Compositional meaning representation: Build logical forms, predicate-argument structures, frames, or graphs. Asha opened the door can be represented as open(e, Asha, door) with past time.
6. Selectional restrictions and plausibility: Detect that The stone ate the book conflicts with ordinary animate-agent expectations, while recognizing that metaphor may deliberately violate them.
7. Negation, modality, and quantifier scope: Distinguish Ravi did not leave, Ravi may leave, and scope alternatives in Every student read a book.
8. Semantic similarity and textual entailment: Decide whether A dog barked entails An animal made a sound, contradicts it, or is unrelated, depending on the representation and knowledge used.

Example. For The bank approved the loan, POS tagging yields determiner–noun–verb–determiner–noun; syntax identifies bank as subject and loan as object; WSD selects the financial sense; semantic roles identify the approving organization and approved object; a knowledge base may normalize the bank to an institution. Semantics remains uncertain when context is missing, and pragmatic/discourse processing may be needed for references or implied meaning. The layered account is consistent with Jurafsky & Martin and the syllabus’s semantic-analysis topics.

6. Explain the history and origin of Natural Language Processing and explain the major developments in NLP from rule-based systems to modern AI-based systems.

Answer. Natural Language Processing arose at the intersection of linguistics, artificial intelligence, computer science, and information theory. Its history is a shift in how linguistic knowledge is represented: hand-written rules, statistical evidence, learned representations, and large pretrained models. The stages overlap; modern systems still use rules, grammars, lexicons, and finite-state tools where they are useful.

Developmental logic. A rule system might encode if “raised its rate” occurs, interpret bank as FINANCE; a bigram model estimates local probabilities from corpus counts; a neural model learns distributed contextual features; a transformer can use much wider context through self-attention. Each system estimates regularities rather than acquiring human-like understanding automatically.

Modern AI therefore does not make earlier knowledge irrelevant. Tokenizers, morphological analyzers, lexicons, constraints, retrieval, and interpretable evaluations remain important. A fair history states both capability and limitation for each era. The historical overview and model trade-offs are treated in Jurafsky & Martin, Speech and Language Processing and Manning & Schütze.

7. Explain why linguistic knowledge and grammar are important in Natural Language Processing. Also explain the role of phonology, morphology, syntax, semantics, discourse, and pragmatics.

Answer. Language is productive, structured, ambiguous, and context-dependent. Linguistic knowledge constrains the enormous number of possible interpretations and helps an NLP system generalize beyond sentences seen in training. A grammar is a formal account of allowable structures and their composition; for example, S -> NP VP says that a sentence can contain a noun phrase and a verb phrase. Grammar generates or filters structures, while probabilities, meaning, discourse, and world knowledge rank interpretations.

Why grammar matters:

1. It supplies reusable structure rather than memorizing every sentence.
2. It reduces ambiguity by ruling out impossible combinations.
3. It supports compositional meaning: the meaning of dog bites man differs from man bites dog because grammar assigns different roles.
4. It supports generation and error detection, such as agreement and word order.
5. It provides interpretable constraints for probabilistic and neural systems.

Grammar alone is insufficient. I saw the man with a telescope may have two grammatical PP attachments; semantic plausibility and context select one. Conversely, a statistically frequent sequence may be ungrammatical in a new context. Modern models distribute much linguistic knowledge across parameters, but explicit levels remain essential for diagnosis, low-resource systems, evaluation, and hybrid pipelines. See Jurafsky & Martin, Ch. 18 for grammar/constituency and Ch. 23 for discourse reference.

8. Design a basic NLP-based system for analyzing customer reviews of an e-commerce website. Explain how the system would process the review through different NLP stages and identify the types of ambiguity it may encounter. Propose suitable techniques to handle these ambiguities.

Answer. The goal is to turn reviews into reliable product, aspect, sentiment, and evidence records. A practical design is:

review + metadata
      -> Unicode/language checks and sentence/token segmentation
      -> normalization, spelling/emoji handling, lemmatization
      -> POS/dependencies and entity/aspect extraction
      -> aspect-based sentiment + negation/sarcasm/context handling
      -> aggregation by product/aspect/time
      -> dashboard, search, alerts, and cited examples

Stage-by-stage design

1. Input and governance: Store review text, product ID, rating, language, timestamp, and consent/retention metadata. Detect language and route regional-language or code-mixed text to suitable models.
2. Cleaning and tokenization: Decode Unicode; preserve negation, ratings, emojis, and punctuation; split sentences and tokens; normalize obvious spelling variants without deleting the original.
3. Morphology and lexical analysis: Lemmatize charging, charged, and charges to useful forms; tag words; detect product names and aspect vocabulary such as battery, screen, delivery, and price.
4. Syntactic analysis: Use dependencies to connect opinion words to aspects: in The camera is surprisingly sharp, link sharp to camera.
5. Semantic processing: Detect aspect spans, polarity, intensity, negation, and comparison. Produce records such as {aspect: battery, sentiment: negative, evidence: “dies quickly”}.
6. Discourse/pragmatics: Link pronouns and repeated mentions, separate multiple sentences/aspects, and detect rhetorical questions or sarcasm.
7. Aggregation and output: Aggregate sentiment by aspect and product while preserving review evidence. Evaluate against an annotated, privacy-safe validation set using aspect extraction F1, sentiment F1, calibration, and slice metrics by language/domain.

Ambiguities and remedies

Use confidence thresholds and human review for high-impact alerts. Do not blindly remove stop words or emojis: they can carry sentiment and negation. A hybrid system combines learned models with lexicons and rules because explicit domain constraints improve interpretability. The application structure follows Jurafsky & Martin and the NPTEL NLP course.

9. Consider the sentence: “I saw the boy with a telescope.” Analyze the sentence at lexical, syntactic, semantic, discourse, and pragmatic levels. Identify the ambiguity present at each applicable level and explain how an NLP system could resolve it.

Answer. The sentence has a classic prepositional-phrase attachment ambiguity, with additional lexical and discourse observations.

Lexical level. saw is ambiguous in isolation: it may be the past tense of see or the noun meaning a cutting tool. In this sentence, I is a pronoun, boy a common noun, telescope a common noun, and with normally a preposition. The surrounding subject and object context makes the verb sense of saw overwhelmingly likely. A lexicon/POS tagger compares candidates using neighboring words and a corpus model.

Syntactic level. There are at least two parses:

Reading A: instrument attachment       Reading B: noun attachment
[S [NP I] [VP saw [NP the boy] [PP with [NP a telescope]]]]
                                          PP modifies boy: the boy had/possessed telescope

[S [NP I] [VP [V saw] [NP the boy [PP with [NP a telescope]]]]]
                                          PP modifies the seeing event: telescope was used

The bracket notation is schematic; the decisive difference is whether with a telescope attaches to VP or NP. A CFG parser generates both if both rules are allowed; a PCFG or discriminative parser ranks them.

Semantic level. Under Reading A, with a telescope is an instrument/means adjunct of the seeing event: see(I, boy, instrument=telescope). Under Reading B, it is a property/associative modifier of the boy: see(I, boy-with-telescope). Selectional and world knowledge may favour the instrument reading because telescopes are instruments for seeing, but the boy-ownership reading is possible.

Discourse level. There is no previous discourse in the isolated sentence, so no antecedent ambiguity is present beyond the definite description the boy, which presupposes a contextually identifiable boy. In a longer discourse, the boy could be linked to a previously introduced boy, and a later he could refer to the boy or the speaker. A coreference resolver uses recency, grammatical compatibility, entity type, and discourse salience.

Pragmatic level. The intended reading depends on the situation. If the speaker is describing astronomy, the instrument reading is natural. If the preceding context says The boy carried a telescope, the noun-attachment reading becomes likely. A speaker’s purpose, visual scene, and shared knowledge can outweigh a generic corpus preference.

Resolution architecture: (1) lexical/POS analysis, (2) produce both parses, (3) score with a PCFG/neural parser, (4) apply semantic role/selectional features, (5) use discourse entities and pragmatic context, and (6) retain uncertainty if evidence is insufficient. Grammar proposes analyses; context chooses among them. This is the standard PP-attachment type discussed in Jurafsky & Martin, Ch. 18.

10. Explain the challenges associated with different stages of Natural Language Processing and write the challenges with suitable examples.

Answer. NLP errors arise from interactions among linguistic variation, limited data, model assumptions, infrastructure, and evaluation. Stage-wise challenges are:

Cross-cutting problems include:

1. Data sparsity and unknown words: finite corpora do not contain every name, inflection, or new term. Use <UNK>, subwords, character features, morphology, smoothing, or adaptation.
2. Domain and temporal shift: a news-trained model may fail on chat or current slang. Use representative splits, domain adaptation, and matched evaluation.
3. Long-range dependencies: first-order models may miss agreement and references separated by many tokens. Use richer features, higher-order/structured models, or contextual encoders.
4. Ambiguity: retain alternatives and rank them using context instead of forcing early irreversible decisions.
5. Low-resource multilingual coverage: languages differ in scripts, morphology, word order, annotation schemes, and available treebanks. Build language-specific resources and evaluate per language.
6. Bias, privacy, and safety: corpora may encode stereotypes or personal information. Document data, audit slices, minimize retention, and provide uncertainty/human review.
7. Evaluation mismatch: one benchmark score can hide subgroup failures, annotation disagreement, leakage, or acceptable alternative outputs. Inspect errors and report robust metrics.

A robust workflow defines the population and task, keeps train/dev/test data separate, tests adversarial and out-of-domain examples, and diagnoses which stage failed. Jurafsky & Martin and Manning & Schütze discuss the statistical and linguistic sources of these challenges.

Module II

11. Explain the Porter Stemming algorithm. Describe the major steps/rules involved and demonstrate its working with suitable examples.

Answer. The Porter stemmer is a deterministic, lexicon-free suffix-stripping algorithm. It maps related surface forms to an index stem, which need not be an English word or a lemma. It is useful in information retrieval for reducing vocabulary variation, but it can over-stem unrelated words and under-stem related words. The original algorithm is Martin Porter’s “An algorithm for suffix stripping”; implementations can differ, so the exact variant should be stated.

Porter represents a word as a sequence of consonant/vowel patterns. Define m as the number of vowel-consonant sequences in the stem. For example, TR has m=0, TREE has m=0, TROUBLES has a larger measure. A rule normally applies only when its stem satisfies a condition such as m > 0; this prevents excessive removal.

Major ordered steps (core rules):

Rules are applied in order, not all at once; order prevents a shorter rule from blocking a longer suffix rule. For a trace, lowercase relational is handled by Step 2: remove/rewrite ational to ate, producing relate; later steps may remove final e depending on m, yielding the algorithm’s stem relat. studies is not simply reduced to study by suffix deletion: spelling alternation and the chosen rule set matter. A common implementation may return stems such as flies -> fli, meeting -> meet, and traditional -> tradit (NLTK stemming documentation).

Advantages: small, fast, no dictionary, useful for recall-oriented search. Limitations: output can be non-words (studies -> studi in some variants), semantic distinctions can be lost, and it does not return features such as N + PL. Therefore, a stemmer is not a lemmatizer or full morphological analyzer.

12. Illustrate tokenization and stemming in NLP using the sentence: “The students are studying Natural Language Processing.” Show the tokens and the resulting stemmed words.

Answer. Assume English tokenization, lowercase normalization for stemming, and the original/standard Porter-style behavior. Keep the final period as a punctuation token; punctuation is not stemmed.

Input: The students are studying Natural Language Processing.

Tokenization:

[The] [students] [are] [studying] [Natural] [Language] [Processing] [.]

A normalized token stream is:

[the, students, are, studying, natural, language, processing, .]

Porter-style stemming:

Thus the resulting sequence is:

[the, student, ar, studi, natur, languag, process, .]

A lemmatizer would give a different, linguistically informed result, approximately [the, student, be, study, natural, language, processing, .], provided POS/context information is supplied. are -> ar demonstrates why stemming is not lemmatization. Tokenization decides boundaries; stemming then applies heuristic normalization to each word. Choices such as keeping punctuation, lowercasing, and removing stop words are task-dependent. See NLTK, Processing Raw Text and the NLTK PorterStemmer API.

13. Explain inflectional and derivational morphology. Differentiate them based on meaning, word class and productivity, with suitable examples.

Answer. Morphology studies the internal structure of words. A morpheme is a minimal meaning- or function-bearing unit; a root is the central lexical element, and an affix is attached to a root/stem. English morphology contains both inflection and derivation.

Inflectional examples:

cat + PL       -> cats       (noun remains N)
walk + PAST    -> walked     (verb remains V)
walk + PROG    -> walking
play + 3SG     -> plays

The form can involve spelling or irregularity: study + 3SG -> studies, go + PAST -> went. A morphological analyzer should output features, not merely delete characters: cats -> cat + N + PL.

Derivational examples:

un- + happy       -> unhappy       (adjective; meaning negated)
happy + -ness    -> happiness      (adjective -> noun)
teach + -er      -> teacher        (verb -> noun/person)
modern + -ize    -> modernize      (adjective -> verb)

Derivation may preserve category (happy -> unhappy) but creates a distinct lexical item. The order can matter: unhappiness = un- + happy + -ness; -ness nominalizes the base. Some forms are lexicalized and cannot be predicted solely from a productive rule.

The distinction is a useful tendency, not an absolute test. -er is comparative inflection in taller but agentive derivation in teacher; -ing can be inflectional in walking and derivational/lexicalized in some nouns. A tokenizer may treat unhappiness as one token even though morphological analysis returns three morphemes. See Jurafsky & Martin, Ch. 2.

14. Explain the role of a Finite State Automaton (FSA) in morphological analysis. Design an FSA that recognizes singular and plural forms of regular nouns such as “cat/cats” and “book/books”.

Answer. A Finite State Automaton (FSA) is a finite set of states with labeled transitions, a start state, and accepting states. It recognizes a regular language: it accepts exactly those strings for which a path consumes every symbol and ends in an accepting state. In morphology, an FSA can recognize legal surface word forms, enforce affix order, and reject malformed forms. An FSA recognizes; an FST additionally maps between surface and lexical representations.

For the requested toy lexicon, use this deterministic FSA. The start state is q0; accepting states are q3 (cat), q4 (cats), q8 (book), and q9 (books).

q0 -c-> q1 -a-> q2 -t-> q3* -s-> q4*
 |
 +--b-> q5 -o-> q6 -o-> q7 -k-> q8* -s-> q9*

The complete non-dead transitions are:

Here q3, q4, q8, and q9 are accepting. All unspecified transitions go to an implicit rejecting/dead state. Thus the FSA accepts cat, cats, book, and books, but rejects catss, catsbook, and bok. To generalize, replace the literal prefix paths with a lexicon sub-automaton and add a plural suffix transition s; to handle city -> cities, add a spelling-alternation path. For morphological analysis, the accepted path can be paired with features: cats -> cat + N + PL. An FSA recognizes surface strings; an FST additionally maps between surface and lexical representations. A finite-state design is efficient and interpretable for regular morphology, but irregular lexemes and productive alternations require additional lexicon/rule paths. Foma’s morphology tutorial illustrates finite-state morphological modeling.

15. Explain the N-gram language model and derive the formula for a bigram model. Discuss how N-gram models can be used for spelling correction, with a suitable example.

Answer. An N-gram language model estimates the probability of a word/token sequence using only a fixed-length history. By the chain rule,

P(w1,...,wT) = product over i of P(wi | w1,...,w(i-1)).

A bigram makes the first-order Markov approximation that the next word depends only on the immediately preceding word:

P(wi | w1,...,w(i-1)) approximately P(wi | w(i-1)).

Therefore, with <s> and </s> included,

P(w1,...,wT, </s> | <s>)
 = P(w1|<s>) P(w2|w1) ... P(wT|w(T-1)) P(</s>|wT).

The unsmoothed maximum-likelihood bigram estimate follows by normalizing continuation counts for a context:

P_MLE(w | h) = count(h,w) / count(h).

For example, if count(the, cat)=4 and count(the)=10, then P(cat|the)=4/10=0.4. Any unseen bigram receives zero in the unsmoothed model, so smoothing/backoff is needed in a real system.

Spelling correction as a noisy-channel application. Let x be the intended word/sentence and y the observed misspelling. Bayes gives

argmax_x P(x|y) = argmax_x P(y|x) P(x).

P(y|x) is the error/channel model; it captures likely substitutions, insertions, deletions, or transpositions. P(x) is the language model; in context, it prefers a fluent candidate. A bigram language model scores the candidate sentence by multiplying its local conditional probabilities.

Example: observed text is I went to teh store.

1. Generate candidates within a small edit distance: the, ten, tech.
2. The channel model may assign high P(teh|the) because adjacent letters were transposed.
3. The bigram context scores P(the|to) and P(store|the); I went to the store is likely.
4. Rank the product, or equivalently the sum of log scores, and replace teh with the if the confidence is sufficient.

Edit distance alone only generates or ranks surface-near candidates; it cannot decide which candidate fits the sentence. A useful corrector combines a language model with the channel model and smoothing. See Jurafsky & Martin, Ch. 3 and Appendix D.

16. Identify and explain five types of referring expressions that can occur in discourse. A conversational NLP system receives the sentence “Ravi submitted his project because he wanted to complete it on time.” Design a simple strategy for resolving pronouns and other referring expressions using contextual information.

Answer. A referring expression identifies or invokes an entity, event, or discourse object. Five common types are:

1. Proper names: Ravi, Delhi, CMC733; normally introduce or retrieve a named entity.
2. Definite descriptions: the project, the student; presuppose a salient, identifiable discourse referent.
3. Indefinite descriptions: a project, an engineer; commonly introduce a new referent, though context can make it specific.
4. Pronouns/anaphors: he, his, it, they; depend on an antecedent and grammatical features.
5. Demonstratives/deictics: this file, that result, here, now; depend on discourse focus or physical situation.

Other phenomena include zero anaphora in some languages, one-anaphora (the red one), and event reference (this decision).

Candidate-resolution strategy:

mention detection -> entity table -> candidate generation
                  -> hard constraints -> salience scoring
                  -> discourse update and confidence threshold

Maintain an entity table with ID, type, number, gender/person where available, grammatical role, sentence position, recency, and current focus. For each pronoun:

1. Generate preceding noun-phrase candidates, including named entities and recently introduced discourse objects.
2. Apply agreement constraints: he/his normally require singular masculine/person-compatible antecedents; it normally selects singular non-human object/event. Do not treat gender as an infallible binary fact; use it as a corpus-dependent feature.
3. Apply syntactic constraints: a pronoun cannot normally refer to an incompatible local binding position; subject/object and clause structure matter.
4. Score candidates by recency, grammatical salience (subject often outranks oblique object), semantic compatibility, repetition, and discourse focus. A Hobbs-like parse-tree search or a learned coreference model can implement this more formally.
5. Resolve only above a confidence threshold; otherwise preserve alternatives or ask for clarification.

For the sentence, update the discourse model as follows:

Ravi                  -> entity E1: PERSON, singular, likely male
his project           -> possessive relation owner(E1, project E2)
he                    -> E1 (agreement + subject salience)
it                    -> E2 (singular project, object of complete)
on time               -> temporal modifier of the completing event

The resulting interpretation is Ravi submitted project E2 because Ravi wanted to complete project E2 on time. The system should not resolve every it to the nearest noun blindly: semantic type and grammatical relation make project better than Ravi. In a larger context, a salient female person or another project could alter the decision. Reference resolution is discussed in Jurafsky & Martin, Ch. 23.

17. Consider the following POS-tagged corpus:

<s> the/DT students/NN pass/V the/DT test/NN </s>
<s> the/DT students/NN wait/V for/P the/DT result/NN </s>
<s> teachers/NN test/V students/NN </s>

Construct a bigram HMM by computing the required transition and emission probabilities. Then use the Viterbi algorithm to determine the most likely POS-tag sequence for:

The students wait for the test.

Answer. Lowercase the test sentence’s initial The to match the training vocabulary, include the boundary tags, and estimate unsmoothed MLE probabilities. Assume the final period is punctuation not represented in the training corpus, so it is consumed as the sentence boundary and is not separately tagged. Unknown emissions would be zero in this unsmoothed toy HMM; smoothing would be required for an operational tagger.

1. Transition probabilities. Count tag-to-tag transitions:

• <s> -> DT: 2; <s> -> NN: 1; total 3.
• DT -> NN: 4; total outgoing from DT = 4.
• NN -> V: 3 (students, students, teachers); NN -> </s>: 3 (test, result, final students); total 6.
• V -> DT: 1; V -> P: 1; V -> NN: 1; total 3.
• P -> DT: 1; total 1.

Thus:

There is no transition from DT to any tag other than NN, and no observed V -> </s> in this corpus.

2. Emission probabilities. Count words emitted by each tag:

• DT: the occurs 4 times, so P(the|DT)=4/4=1.
• NN: six tokens: students 3, test 1, result 1, teachers 1.
• V: pass, wait, test, each once out of 3.
• P: for once out of 1.

3. Viterbi calculation. Let V_i(t) be the best probability for the first i words ending in tag t:

V_1(t) = P(t|<s>) P(w1|t)
V_i(t) = max_u V_(i-1)(u) P(t|u) P(wi|t)

Only non-zero cells are shown because each observed word has a unique non-zero lexical tag in this corpus.

The backpointers give:

DT -> NN -> V -> P -> DT -> NN -> </s>

Therefore the most likely POS sequence is:

The/DT students/NN wait/V for/P the/DT test/NN ./. 

The probability 1/648 is the joint path probability under the toy model (excluding a separately modeled period). A smoothed model could give non-zero alternatives and potentially change a choice; Viterbi still selects the highest-scoring complete sequence. HMM definitions and Viterbi recurrence are given in Jurafsky & Martin, Ch. 17 and Appendix A.

18. Design a Finite State Transducer (FST) for recognizing and generating regular noun plural forms. Clearly show the states, transitions and input/output symbols for words such as “cat → cats” and “book → books”.

Answer. An FST is an automaton whose transitions consume an input symbol and emit an output symbol. For morphology, use the lexical tape as input and the surface tape as output. The relation should accept singular lexical forms such as cat and book, and plural analyses cat+PL and book+PL while generating cats and books.

For a compact toy lexicon:

Input: lexical representation       Output: surface word

q0 -c:c-> q1 -a:a-> q2 -t:t-> q3*       cat -> cat
q3 -+PL:epsilon-> q4 -epsilon:s-> q5*    cat+PL -> cats

q0 -b:b-> q6 -o:o-> q7 -o:o-> q8 -k:k-> q9*  book -> book
q9 -+PL:epsilon-> q10 -epsilon:s-> q11*      book+PL -> books

* means accepting. The transition table is:

Running the FST forward generates:

cat       -> cat
cat+PL    -> cats
book      -> book
book+PL   -> books

Running the same relation backwards analyzes cats as cat+PL and books as book+PL, assuming the lexicon path is available. A practical FST factors out the letter-copying lexicon, adds a plural suffix subnetwork, and includes orthographic alternations such as city+PL -> cities. Epsilon transitions are useful because the lexical feature +PL is not itself printed on the surface. FSTs can be composed from lexicon, morphotactics, and spelling-rule components; Foma’s FST morphology tutorial gives this analysis/generation perspective.

19. Explain the concept of Bigram and N-gram models with formulas. Apply a Bigram model to the given corpus.

Answer. An N-gram model approximates the probability of the next token using the previous N-1 tokens. A unigram uses no history, a bigram uses one previous token, and a trigram uses two. By the chain rule and first-order Markov approximation:

P(w1,...,wT) = product_i P(wi | w1,...,w(i-1))
P_bigram(w1,...,wT) = P(w1|<s>) product_(i=2..T) P(wi|w(i-1)) P(</s>|wT)
P_MLE(w|h) = count(h,w)/count(h).

Use the supplied corpus without smoothing. The relevant continuation counts are:

1. Most probable next word

a) <s> Sam...... The current history is Sam. The candidates are I with probability 3/5 and </s> with 2/5; therefore the prediction is I.

b) <s> Sam I do...... A bigram ignores all but the last word do. P(I|do)=1/2 and P(like|do)=1/2. Therefore this is a tie between I and like. The model cannot use the longer prefix to break the tie.

c) <s> Sam I am Sam..... Again the last word is Sam; the prediction is I, with probability 3/5.

d) <s> do I like.... The last word is like. P(</s>|like)=2/3 and P(Sam|like)=1/3; the most probable next symbol is </s>, meaning the sentence ends.

2. Sentence comparison

Include all boundary transitions and use the unsmoothed model:

e. <s> Sam I do I like </s>

P = P(Sam|<s>) P(I|Sam) P(do|I) P(I|do) P(like|I) P(</s>|like)
  = (3/5)(3/5)(1/5)(1/2)(2/5)(2/3)
  = 6/625 = 0.0096.

f. <s> Sam I am </s>

P = (3/5)(3/5)(2/5)(1/2)
  = 9/125 = 0.072.

g. <s> I do like Sam I am </s>

P = (1/5)(1/5)(1/2)(1/3)(3/5)(2/5)(1/2)
  = 1/1250 = 0.0008.

Hence the ranking is f > e > g. The bigram model assigns zero to any sentence containing an unseen adjacent pair; smoothing would avoid zero probabilities and could alter comparisons in a sparse corpus. See Jurafsky & Martin, Ch. 3.

20. Consider the following corpus:

<s> I tell you to sleep and rest </s>
<s> I would like to sleep for an hour </s>
<s> Sleep helps one to relax </s>

• a) List all possible bigrams.
• b) Compute the conditional probabilities.
• c) Predict the next word after the word “to” using the bigram model.

Answer. Assume case normalization, so sentence-initial Sleep is counted as sleep, and use unsmoothed MLE counts. Boundary symbols are included.

a) Unique bigrams and counts

<s> I                 (2)
<s> sleep             (1)
I tell                (1)
I would              (1)
tell you              (1)
you to                (1)
to sleep              (2)
to relax              (1)
sleep and             (1)
sleep for             (1)
sleep helps           (1)
and rest              (1)
rest </s>             (1)
would like            (1)
like to               (1)
for an                (1)
an hour               (1)
hour </s>             (1)
helps one             (1)
one to                (1)
relax </s>            (1)

These are 21 distinct bigram types. The repeated type to sleep occurs twice.

b) Conditional probabilities

Normalize each row by the count of its history word:

| History h | Continuations and probabilities P(w|h) | |---|---| | <s> (3) | P(I|<s>)=2/3, P(sleep|<s>)=1/3 | | I (2) | P(tell|I)=1/2, P(would|I)=1/2 | | tell (1) | P(you|tell)=1 | | you (1) | P(to|you)=1 | | to (3) | P(sleep|to)=2/3, P(relax|to)=1/3 | | sleep (3) | P(and|sleep)=1/3, P(for|sleep)=1/3, P(helps|sleep)=1/3 | | and (1) | P(rest|and)=1 | | rest (1) | P(</s>|rest)=1 | | would (1) | P(like|would)=1 | | like (1) | P(to|like)=1 | | for (1) | P(an|for)=1 | | an (1) | P(hour|an)=1 | | hour (1) | P(</s>|hour)=1 | | helps (1) | P(one|helps)=1 | | one (1) | P(to|one)=1 | | relax (1) | P(</s>|relax)=1 |

All unlisted continuations have probability zero in this unsmoothed model. With add-one smoothing, unobserved words would receive a small non-zero probability, but the listed probabilities would be changed.

c) Prediction after to

to is followed twice by sleep and once by relax, so:

P(sleep|to)=2/3 > P(relax|to)=1/3.

The bigram model predicts sleep. This illustrates corpus sensitivity: the prediction is a property of these counts, not a universal fact about English.

Module III

21. Explain Part-of-Speech (POS) tagging and its significance in Natural Language Processing with suitable examples.

Answer. Part-of-Speech tagging assigns a grammatical/lexical category to each token in context. Formally, for words w1,...,wn, a tagger predicts a sequence t1,...,tn, such as NN, VB, or DT. It is a sequence-labeling problem because the best tag for one word depends on neighboring words and tags.

Common Penn Treebank tags include:

Contextual example:

Book the flight.       Book/VB the/DT flight/NN.
The book is heavy.      The/DT book/NN is/VBZ heavy/JJ.

The spelling book does not have one permanent POS; its syntactic context changes its tag. Similarly, Can you can the can? can be tagged approximately Can/MD you/PRP can/VB the/DT can/NN ?/..

Significance:

1. POS tags provide features for parsing, chunking, named-entity recognition, information extraction, and translation.
2. They distinguish grammatical roles and reduce lexical ambiguity for later stages.
3. They support lemmatization: saw may be see/VBD or saw/NN depending on tag/context.
4. They reveal morphology such as tense, number, and participles.
5. They support grammar checking and language-model features.

Challenges include unknown words/names, spelling variation, contractions, punctuation, domain shift, code-switching, ambiguous word forms, and annotation differences. The tagset is an annotation convention, not a universal inventory. NLTK’s Penn Treebank documentation and Jurafsky & Martin, Ch. 17 describe tagging and tagsets.

22. Explain the limitations of the Hidden Markov Model (HMM) when applied to Part-of-Speech tagging.

Answer. In an HMM POS tagger, tags are hidden states and words are observations. A first-order model scores a tag sequence as:

P(t1,...,tn,w1,...,wn)
 = product_i P(ti | t(i-1)) P(wi | ti).

Viterbi finds the highest-probability path, but the result is limited by the model assumptions:

1. First-order Markov assumption: P(ti|t1,...,t(i-1)) is reduced to P(ti|t(i-1)). A tag may depend on two or more previous tags, clause structure, or long-distance agreement, which a bigram transition cannot express.
2. Conditional independence of observations: Given a tag, the word is assumed independent of neighboring words and broader context. The emission P(word|tag) cannot directly represent previous word=to, capitalization, suffix, or semantic context unless these are encoded indirectly.
3. Generative modeling burden: HMM models the joint P(words,tags) even though tagging needs P(tags|words). It must model the distribution of all possible words, wasting capacity on irrelevant distinctions.
4. Data sparsity and zero probabilities: Unseen transitions or emissions receive zero under MLE; one zero factor makes a whole path impossible. Smoothing and interpolation are necessary.
5. Unknown words/OOV: A word absent from training has no emission. Names, typos, new verbs, and technical words are common. Suffix, capitalization, digit, hyphen, and subword classes are needed as backoff features.
6. Weak feature representation: HMMs do not naturally use overlapping arbitrary features such as word=book, previous=to, capitalized, and next suffix=-ing together. Discriminative MaxEnt/CRF models handle these more directly.
7. Ambiguous or noisy annotation: Corpora contain tagging conventions and disagreements; the HMM learns their biases rather than a universal grammar.
8. Domain and language shift: Counts from news may not describe chat, biomedical text, code-mixing, or a morphologically rich language.
9. Local tagset assumptions: The tagset may be too coarse or too English-specific for another language.
10. Best path is model-relative: Viterbi returns the best sequence under estimated probabilities, not necessarily the linguistically true interpretation.

HMMs remain valuable because they are mathematically clear, efficient, and effective with sufficient data and good smoothing. Hybrid systems add unknown-word classes, higher-order transitions, or discriminative features. Jurafsky & Martin, Ch. 17 and Appendix A give the HMM factorization and decoding assumptions.

23. Explain the major challenges encountered in Part-of-Speech (POS) tagging. Also explain how lexical ambiguity and unknown words affect POS tagging accuracy.

Answer. POS tagging is difficult because a tag is assigned to a word in context, while both word forms and contexts vary.

Major challenges

1. Lexical ambiguity: book is NN in the book and VB in book a ticket; can may be modal, verb, or noun; watch may be noun or verb.
2. Unknown words: names (Aaradhya), new products, typos, hashtags, and technical terms have no lexical emission counts. The tagger must use suffix, capitalization, digits, hyphens, shape, and neighboring tags.
3. Morphological variation: walked, walking, studies, irregular forms, compounds, and rich inflection create unseen or ambiguous forms.
4. Context length: agreement and category may depend on a distant word or clause, beyond a local window.
5. Tokenization/contractions: can't, New York, URLs, emojis, and punctuation require a compatible token policy.
6. Domain/genre shift: news-trained distributions differ from conversation, social media, legal, or scientific text.
7. Code-switching and multilingual text: tagsets, scripts, word order, and morphological categories may change mid-sentence.
8. Ambiguous annotation: different corpora may label -ing, particles, or foreign words differently.
9. Proper names and capitalization: sentence position and all-caps writing can destroy capitalization cues.
10. Efficiency and robustness: a system must decode quickly and remain calibrated on rare cases.

Effect of lexical ambiguity

A word with several possible tags has an emission probability for each tag. For book, an HMM might have both P(book|NN) and P(book|VB) non-zero. Lexical evidence alone cannot choose; transition/context evidence is required. In to book, P(VB|TO) makes VB likely; in the book, P(NN|DT) makes NN likely. A tagger that uses only the most frequent dictionary tag fails whenever the less frequent sense occurs.

Effect of unknown words

For an OOV word, a simple HMM has P(unknown|tag)=0 for every tag, so every sequence containing it gets probability zero. A robust tagger maps rare words to <UNK> classes or estimates emissions from word shape:

unknown -> suffix/prefix, capitalization, digit, hyphen, character/subword pattern
          + neighboring words/tags + lexical embeddings

For example, an unknown capitalized token after Mr. is likely NNP; an unknown -ed form is often VBD/VBN; an unknown -ly form is often RB, though exceptions exist. Use probabilities, not hard rules, because friendly is an adjective and Google can be a verb. Smoothing, suffix models, character features, subword representations, and domain adaptation reduce the damage. Report OOV accuracy separately, because overall accuracy can conceal most errors on rare words. See Jurafsky & Martin, Ch. 17.

24. Compare top-down and bottom-up parsing approaches with suitable examples and also write the advantages and limitations of each approach.

Answer. Parsing searches for a derivation of an input string using a grammar. Top-down parsing starts with the start symbol and predicts structures; bottom-up parsing starts with input words and combines recognized constituents.

Use the grammar:

S  -> NP VP
NP -> Det N
VP -> V
Det -> the
N -> dog
V -> sleeps

Top-down derivation:

S => NP VP
  => Det N VP
  => the N VP
  => the dog VP
  => the dog V
  => the dog sleeps

It begins with the goal S, predicts NP and VP, and matches terminals to the input.

Bottom-up construction:

scan the -> Det
scan dog -> N
reduce Det N -> NP
scan sleeps -> V
reduce NP V -> S   (for a toy VP/grammar equivalence, or use VP -> V first)

In a fully literal grammar, reduce V -> VP before NP VP -> S; the principle is that input symbols are recognized first and then combined upward.

Top-down parsing is particularly effective with a factored LL(1) grammar and one-symbol lookahead. It requires no left recursion and no FIRST/FIRST conflict for deterministic choice. Bottom-up CYK is exhaustive and guarantees recognition for a CNF grammar in cubic chart time; shift-reduce is incremental but must resolve shift/reduce and reduce/reduce conflicts. Both may produce multiple trees, so PCFG probabilities or discriminative scores are used for disambiguation. Jurafsky & Martin, Ch. 18 covers both search directions and constituency parsing.

25. Explain the Maximum Entropy Model for POS tagging. Describe the role of contextual features in predicting the POS tag of a word.

Answer. A Maximum Entropy (MaxEnt) model is a discriminative conditional model. It estimates the probability of a tag y given an observation/context x while making no unnecessary independence assumptions beyond the selected features. For a tag set Y:

P(y | x) = exp(sum_k theta_k f_k(x,y)) / Z(x)
Z(x) = sum_(y' in Y) exp(sum_k theta_k f_k(x,y'))

f_k(x,y) is usually a binary or numeric feature that fires when a condition is true for candidate tag y; theta_k is learned from an annotated corpus. Training maximizes conditional log-likelihood, usually with L1/L2 regularization to prevent overfitting. Prediction chooses argmax_y P(y|x).

Contextual features for the word book:

f(word=book, y=NN)
f(previous_word=the, y=NN)
f(previous_tag=DT, y=NN)
f(previous_word=to, y=VB)
f(next_word=the, y=VB)
f(suffix=ook, y=NN or VB)
f(capitalized, y=NNP)
f(word_shape, y)
f(next_tag or neighboring context, y)

For The book is heavy, features previous_word=The, previous_tag=DT, and next_word=is raise the NN score. For to book a flight, previous_word=to and next_word=a raise the VB score. Overlapping evidence is added in the exponent, so a model can combine lexical, morphological, orthographic, and neighboring cues instead of relying on one independence assumption.

Training/inference steps:

1. Extract features for every candidate tag in each annotated training sentence.
2. Learn weights so features correlated with correct tags get positive weights and misleading features get negative weights.
3. At test time, calculate each candidate’s weighted score and normalize with Z(x).
4. Select the highest-probability tag; use regularization and held-out data for calibration.

A token-level MaxEnt tagger predicts labels independently or with locally supplied previous-tag features. If previous predicted tags are used, errors can propagate and local normalization can cause label bias. A sequence model such as a CRF globally scores the entire tag sequence and uses transition features. MaxEnt is flexible and interpretable at the feature level, but depends on feature engineering, labeled data, and a suitable handling of sequence dependencies. The conditional-model formulation is described in Jurafsky & Martin, Ch. 17.

26. Demonstrate the concept of Conditional Random Field (CRF) in NLP. Explain how CRF can be used for sequence labeling tasks such as POS tagging and Named Entity Recognition.

Answer. A Conditional Random Field directly models the conditional probability of a complete label sequence y given an observed sequence x. It is discriminative: it does not need to model P(x).

For a linear-chain CRF with labels y1,...,yn,

P(y|x) = exp(score(x,y)) / Z(x)
score(x,y) = sum_i sum_k theta_k f_k(y_(i-1), yi, x, i)
Z(x) = sum over all possible y' exp(score(x,y'))

Features may refer to the current word, neighboring words, prefixes/suffixes, capitalization, character shape, previous/current labels, and arbitrary overlapping observations. Transition features can reward or penalize label sequences. Z(x) globally normalizes all complete sequences.

POS tagging with a CRF

For to book the flight, a CRF can include:

word_i=book and yi=VB
previous_word=to and yi=VB
previous_tag=TO and yi=VB
yi-1=DT, yi=NN
suffix=-ing and yi=VBG
capitalized and yi=NNP

Viterbi decoding finds the highest-scoring tag sequence. Forward-backward computes the partition function and marginal probabilities. If TO -> VB is common and DT -> NN is common, transition features encourage globally coherent tags rather than making isolated choices.

NER with a CRF

Represent labels in BIO form:

Riya emailed Prof. Sen
B-PER O       B-PER I-PER

Word shape, capitalization, prefixes/suffixes, gazetteer matches, context words, and label transitions help. A CRF can learn that I-ORG should normally follow B-ORG/I-ORG, while I-PER cannot begin an entity. The transition feature and global normalization make invalid or unlikely sequences less competitive.

CRF training and inference

1. Prepare annotated sequences and extract feature functions.
2. Optimize regularized conditional log-likelihood; gradients require expected feature counts from forward-backward.
3. Decode the best sequence with Viterbi, or compute marginals for uncertainty.
4. Evaluate sequence/entity-level precision, recall, and F1 rather than only token accuracy.

Advantages: rich overlapping input features, direct conditional objective, and coherent global label decisions. Limitations: feature design and training cost, dependence on labeled data, and possible domain shift. A CRF avoids the classic local-normalization label-bias issue of locally normalized sequence classifiers, though modern neural encoders often supply the features. The original model is Lafferty, McCallum & Pereira (2001); the sequence-labeling treatment is also in Jurafsky & Martin, Ch. 17.

27. Consider the following corpus:

N (Noun): Martin, Justin, Will, Spot, Pat
M (Modal Verb): can, will
V (Verb): watch, spot, pat

Construct the transition probability matrix and emission probability matrix for the corresponding HMM. Clearly state any assumptions made for calculating the probabilities.

Answer. The supplied information is a lexicon, not a tagged sequence corpus, so transition probabilities cannot be uniquely computed from it. Also, Will occurs under N and M, while Spot and Pat occur under N and V; this explicitly creates lexical ambiguity. I will make a transparent toy assumption so that a valid HMM can be constructed.

Assumption for transitions

Assume the lexicon is used to generate a set of sentences with the fixed grammatical tag pattern:

<s> N M V N </s>

For example, Justin can watch Spot or Martin will spot Pat. Assume all such tag sequences have the same structural pattern and counts are proportional to positions. The first N begins after <s>; the second N ends before </s>. Therefore transition counts per generated sentence are:

<s> -> N       1
N -> M         1
M -> V         1
V -> N         1
N -> </s>      1

There are two outgoing N occurrences (the initial N followed by M and final N followed by </s>), so P(M|N)=1/2 and P(</s>|N)=1/2.

Transition probability matrix

Each row sums to one. Unobserved transitions have zero probability in this unsmoothed toy model. Other assumptions (for example, a corpus containing multiple templates) would produce different matrices and should be stated.

Emission probability matrix

Assume each word listed under a tag is emitted uniformly within that tag’s inventory. Shared surface words are retained under every listed tag rather than being forced to one category:

| Word | P(word|N) | P(word|M) | P(word|V) | |---|---:|---:|---:| | Martin | 1/5 | 0 | 0 | | Justin | 1/5 | 0 | 0 | | Will/will | 1/5 | 1/2 | 0 | | Spot/spot | 1/5 | 0 | 1/3 | | Pat/pat | 1/5 | 0 | 1/3 | | can | 0 | 1/2 | 0 | | watch | 0 | 0 | 1/3 |

The N row has five entries, the M row two, and the V row three; each row sums to one. Case is normalized for probability calculation, so Will/will is one spelling. In a real corpus, emissions would be learned from tagged counts rather than assumed uniform, and smoothing/unknown-word features would be needed.

This model intentionally encodes ambiguity: will can be N or M, and spot/pat can be N or V. The fixed transition pattern supplies the structural preference that will be used in the next question.

28. Using the HMM constructed from the given corpus, apply the Viterbi algorithm to perform POS tagging for the sentence:

Justin will spot Will.

Show the transition probabilities, emission probabilities, Viterbi calculations, and the most probable POS-tag sequence.

Answer. Use the HMM and assumptions from Question 27: the structural pattern is <s> N M V N </s>, transition rows are unsmoothed, and emissions are uniform within each tag inventory. Normalize case and treat the period as a boundary symbol rather than a separate trained emission.

Relevant transitions:

P(N|<s>) = 1
P(M|N) = 1/2
P(V|M) = 1
P(N|V) = 1
P(</s>|N) = 1/2

Relevant emissions:

P(Justin|N) = 1/5
P(will|M) = 1/2; P(will|N) = 1/5
P(spot|V) = 1/3; P(spot|N) = 1/5
P(Will|N) = 1/5; P(Will|M) = 1/2

Let delta_i(t) be the best path probability ending at tag t for word i:

delta_1(t) = P(t|<s>) P(w1|t)
delta_i(t) = max_u delta_(i-1)(u) P(t|u) P(wi|t)

The backtrace is:

<s> -> N -> M -> V -> N -> </s>

Therefore:

Justin/N will/M spot/V Will/N ./.

The lexical ambiguities are resolved by transition structure: will is modal after an N, spot is a verb after M, and final Will is a noun/name after V. The probability 1/600 is for the four-word tag path plus boundary under this toy model. With smoothing, other paths would be non-zero, but the most likely path would still be obtained by comparing all candidates with Viterbi.

29. For the following Context-Free Grammar (CFG), construct the CYK/CKY parsing table and determine whether the sentence

The man read this book

can be generated by the grammar. Show all intermediate steps.

• Note: Specify suitable CNF production rules for the sentence.

Answer. Since no productions are supplied, specify a suitable grammar in Chomsky Normal Form (CNF). CNF permits binary nonterminal rules A -> BC and lexical rules A -> word; the preterminal lexical rules are allowed in the usual CKY presentation.

S  -> NP VP
VP -> V NP
NP -> Det N
Det -> The
Det -> this
N   -> man
N   -> book
V   -> read

This grammar generates exactly the desired structure:

S
├── NP
│   ├── Det -> The
│   └── N   -> man
└── VP
    ├── V   -> read
    └── NP
        ├── Det -> this
        └── N   -> book

Number tokens from 1 to 5:

1 The   2 man   3 read   4 this   5 book

For CKY, C[i,j] contains the nonterminals that span tokens i through j. For every binary rule A -> BC, try each split k:

if B in C[i,k] and C in C[k+1,j], add A to C[i,j].

Length-1 cells (lexical initialization)

Length-2 cells

Length-3 cells

Length-4 cells

Length-5 cell

A triangular CKY summary is:

                         [1,5] {S}
                 [1,4] {}              [2,5] {}
          [1,3] {} [2,4] {}       [3,5] {VP}
 [1,2] {NP} [2,3] {} [3,4] {} [4,5] {NP}
[1,1]{Det} [2,2]{N} [3,3]{V} [4,4]{Det} [5,5]{N}

Because [1,5] contains S, the sentence can be generated. Backpointers recover S -> NP VP, NP[1,2] -> Det N, VP[3,5] -> V NP, and NP[4,5] -> Det N. A strict implementation must either eliminate unit/preterminal details in advance or include lexical initialization/closure as shown. CKY’s binary-span recurrence and CNF requirement are described in Jurafsky & Martin, Ch. 18 and Appendix F.

30. Design a POS-tagging approach for a conversational NLP system that frequently encounters ambiguous words such as “can”, “will”, “spot”, and “watch”. Compare how an HMM, Maximum Entropy model, and CRF could handle the ambiguity and justify the most suitable approach.

Answer. Design the system as a context-sensitive sequence tagger with a domain-specific tagset and a safe fallback. The ambiguous inventory illustrates the alternatives:

Can you can the can?       MD  PRP VB  DT  NN
Will will watch Spot.      N   MD  VB  N  (example-dependent)
I watch the spot.          PRP VB  DT  NN
The watch can spot flaws.  DT  NN  MD  VB  NNS

Proposed pipeline

conversation/audio -> ASR + punctuation/confidence
                    -> tokenization and speaker/turn context
                    -> spelling/subword normalization
                    -> HMM/MaxEnt/CRF tagger
                    -> dialogue state, parser, intent/entity modules
                    -> confidence-aware response/action

Use training data from the actual conversational domain, annotated with Penn-style tags plus dialogue features. Include previous/next words, previous/next tags, capitalization, suffix/prefix, word shape, speaker turn, question/imperative status, ASR confidence, and dialogue state. Keep the original text so normalization does not erase distinctions.

HMM comparison

An HMM estimates:

P(tag sequence, words) = product_i P(ti|t(i-1)) P(word_i|ti).

It can learn P(MD|START), P(VB|MD), P(NN|DT), and emissions for can, will, spot, and watch. Viterbi chooses the best complete path, so can after you and before the is likely VB, while can before a base verb is likely MD. It is fast, transparent, and works well with sufficient tagged data. However, first-order transitions and independent emissions cannot naturally combine many overlapping conversational cues; OOVs, ASR errors, and zero counts require smoothing and unknown-word classes.

Maximum Entropy comparison

A token-level MaxEnt model uses:

P(t|x) = exp(sum_k theta_k f_k(x,t)) / Z(x).

Useful features include word=can, previous=you, next=the, previous_tag=PRP, next_tag=DT, question, suffix, and ASR confidence. It can directly learn that can after you and before a determiner is often VB, while can before watch is MD; watch after the is NN, but after I is VB. It handles overlapping lexical, orthographic, and discourse features better than a basic HMM. A standalone token classifier, however, does not globally enforce a consistent tag sequence; previous predicted labels can propagate errors and local normalization can create label bias.

CRF comparison

A linear-chain CRF models:

P(y|x) = exp(score(x,y)) / sum_y' exp(score(x,y')).

It combines the same rich word/context/turn/ASR features with transition features such as MD -> VB, PRP -> VB, DT -> NN, and DT -> VB penalties. Viterbi jointly decodes the whole utterance, so it can distinguish:

Can/MD you/PRP can/VB the/DT can/NN ?
I/PRP watch/VB the/DT spot/NN .
The/DT watch/NN can/MD spot/VB flaws/NNS .

It is globally normalized over sequences and can represent BIO/entity constraints if the conversational system also extracts entities. Forward-backward supplies uncertainty, which is important when ASR or context is unreliable.

Recommendation

Choose a linear-chain CRF, preferably with a neural/character encoder supplying robust features if sufficient labeled conversational data is available. It is the best fit because ambiguity depends on overlapping local observations and coherent neighboring tags, and it allows confidence-aware sequence decisions. Use an HMM as a transparent baseline and low-resource fallback; use MaxEnt as a strong token-level baseline or feature analysis tool. Add:

1. smoothed emissions/unknown-word classes or character features;
2. domain and speaker-turn adaptation;
3. ASR-confidence features and N-best hypotheses;
4. a reject/clarify policy for low confidence;
5. evaluation by ambiguous-word accuracy, OOV accuracy, full-sentence accuracy, macro F1, and slices by speaker/accent/domain.

A modern transformer-encoder-plus-CRF can replace manual feature extraction, but the HMM/MaxEnt/CRF conceptual comparison remains: HMM is generative and locally Markovian; MaxEnt is discriminative and usually local; CRF is discriminative and globally sequence-structured. The CRF formulation is grounded in Lafferty, McCallum & Pereira (2001), while HMM and sequence-labeling details appear in Jurafsky & Martin, Ch. 17.

Verification checklist

• Questions 1–30 are present in numerical order.
• Every question is followed immediately by a complete exam-ready answer.
• Worked probability calculations, Viterbi traces, FSA/FST designs, and CKY chart are included.
• Assumptions and unsmoothed zero-probability behavior are stated where inputs are underspecified.
• Frontmatter is preserved with updated: 2026-08-12 and status: complete.