Natural Language Processing · TEE · papers

Q6B · Hobbs: Ramesh and Shyam

Solved re-exam · February 2026

Actual re-examination · 9 February 2026 · 100 marks · 3 hours

Question. i. Explain Hobbs’ Algorithm for pronoun resolution. State its main steps and limitations.
ii. Apply Hobbs’ Algorithm to the sentence: “When Ramesh gave Shyam a book, he smiled.” Identify the antecedent of “he” by showing traversal steps. [10 marks]

Answer

Hobbs’ algorithm is a syntax-based pronoun-resolution procedure that searches constituency parse trees in a specified order. It proposes noun phrases as antecedents and filters incompatible candidates, for example by number and gender agreement.

Read the tree labels first: NP means noun phrase; S means sentence/clause; VP means verb phrase. X is the current NP or S search node, and p is the upward path used to reach it. Breadth-first means shallower nodes before deeper nodes; left-to-right fixes the order at the same depth. An N-bar (N′) node is the noun-centred part of an NP in a parse using that label.

Complete ordered procedure

Locate the pronoun. Start at the NP immediately dominating the pronoun: the smallest NP containing it.
Make the first climb. Move upward to the first NP or S above the starting NP. Call it X and record the path p.
Search initially to the left. Traverse branches below X to the left of p, breadth-first and left-to-right. Propose an NP only if another NP or S lies between that candidate and X. Check agreement and other applicable constraints for each proposed candidate; accept the first eligible compatible one.
Check the highest sentence. If X is the highest S and no candidate has been accepted, search previous sentence trees, most recent first. In each, traverse breadth-first and left-to-right and propose NPs. Accept the first eligible compatible candidate; if the available context contains none, report no resolved antecedent.
Otherwise climb again. Move from X to the next NP or S above it. Make that node the new X and record the new upward path p.
Test a higher NP. If the new X is an NP, propose X only when p did not pass through its nominal N-bar child. Apply the same compatibility checks. Use the labels in the supplied parse; do not invent a missing N-bar branch.
Search left again. Traverse the new X’s branches to the left of p, breadth-first and left-to-right, proposing NPs. The extra intervening-NP/S requirement in Step 3 belongs to the initial search.
Search permitted right branches. If X is an S, traverse branches to the right of p, breadth-first and left-to-right, but do not descend below any NP or S encountered. Propose the encountered eligible NPs and test their compatibility.
Repeat or finish. Return to Step 4 until a compatible candidate is accepted or the available sentence trees are exhausted. Record the candidate order and why each candidate was accepted or rejected.

Why the initial restriction matters: in “John saw him”, the subject NP John is directly under the clause S, with no additional NP or S between them. Step 3 therefore does not propose John as the ordinary local antecedent of him. A reflexive such as himself is a different grammatical case. The worked question below shows the specific parse and traversal; selecting an antecedent is not simply choosing the nearest name.

Given

The pronoun he is the subject of the main clause. The preceding subordinate clause is “When Ramesh gave Shyam a book”. Assume the temporal clause attaches to the whole main sentence.

To find

The first suitable antecedent in the left-to-right breadth-first search of the preceding clause.

S (main)                        ← first X
├── SBAR: When
│   └── S (embedded)             ← intervening S
│       ├── NP: Ramesh           ← first candidate
│       └── VP
│           ├── V: gave
│           ├── NP: Shyam
│           └── NP: a book
├── NP: he                      ← start
└── VP: smiled

Step 1. Locate the pronoun NP

Start at NP “he” and move upward to its S ancestor. Record the path from he.

Step 2. Search branches before the pronoun

The initial when-clause lies to the left of the path. Apply Step 3: its embedded S lies between each of its noun phrases and the main S, so these NPs satisfy the initial intervening-NP/S requirement. Traverse left-to-right and breadth-first.

Step 3. Propose noun phrases

The subject NP Ramesh is encountered before the deeper object NP Shyam and object NP a book. Ramesh agrees with the assumed singular-male pronoun.

Step 4. Accept the first compatible antecedent

Select Ramesh. Shyam is also a semantically possible referent in ordinary discourse, but the algorithm’s stated syntactic preference selects Ramesh first.

Limitations

Requires a suitable and accurate constituency parse.
Agreement information may be unknown or insufficient when several people match.
Ignores much of the event semantics, discourse focus and world knowledge.
An ambiguous parse or different attachment can change candidate order.

Final answer: Ramesh, under the shown parse and ordinary agreement assumptions. A syntactic preference is not a guarantee about the author’s intended meaning.

Yaad rakho: Left branches ko breadth-first dekho; pehla eligible matching NP choose karo.