Project ForgeA lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.
T1: a?(b|c)*a T2: b?(a|c)*b T3: c?(b|a)*c
('x?' means 0 or 1 occurrence of x.) The analyzer outputs the token matching the longest possible prefix. If the string bbaacabc is processed, which one of the following is the sequence of tokens it outputs?
- AT1T2T3
- BT1T1T3
- CT2T1T3
- T3T3
Explanation
From position 0 ('bbaacabc'): T1 matches 'bba' (3 chars, optional-a absent, (b|c)* takes 'bb', then mandatory 'a'). T2 matches 'bb' (2 chars). T3 matches 'bbaac' (5 chars: optional-c absent, (b|a)* greedily takes 'bbaa', then mandatory 'c') — T3 wins as the longest. Remaining string 'abc': T1 can only match 'a' (1 char, no second 'a' available). T2 matches 'ab' (2 chars). T3 matches 'abc' (3 chars: (b|a)* takes 'ab', then mandatory 'c') — T3 wins again. Token sequence: T3, T3.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.