A lexical analyzer uses the following patterns to recognize three tokens T1,…
2018
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.
𝑇1: 𝑎? (𝑏|𝑐)∗𝑎
𝑇2: 𝑏? (𝑎|𝑐)∗𝑏
𝑇3: 𝑐? (𝑏|𝑎)∗ 𝑐
Note that ‘\(x\)?’ means 0 or 1 occurrence of the symbol \(x\). Note also that the analyzer outputs the token that matches the longest possible prefix.
If the string 𝑏𝑏𝑎𝑎𝑐𝑎𝑏𝑐 is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
- A.
𝑇1𝑇2𝑇3
- B.
𝑇1𝑇1𝑇3
- C.
𝑇2𝑇1𝑇3
- D.
𝑇3𝑇3
Attempted by 205 students.
Show answer & explanation
Correct answer: D
Key idea: at each position the analyzer picks the token that matches the longest possible prefix.
Step 1 (start at position 1):
T2 can match at most 'bb' (length 2) because (a|c)* cannot include the second 'b'.
T1 can match 'bba' (length 3) but cannot extend because an 'a' appears inside the (b|c)* part.
T3 can match 'bbaac' (length 5) because (b|a)* can cover the interior before the final 'c'.
Pick the longest: T3 matching 'bbaac'.
Step 2 (remaining input 'abc' at positions 6–8):
T1 can only match 'a' (length 1).
T2 can match 'ab' (length 2).
T3 matches 'abc' (length 3) because (b|a)* accepts 'ab' before the final 'c'.
Pick the longest: T3 matching 'abc'.
Final answer: the analyzer outputs the token sequence T3, T3.
A video solution is available for this question — log in and enroll to watch it.