A Scanner That Accepts the Wrong Suffix
A school team designs a lexical scanner for a small language over the alphabet zero and one. The stated task is to accept exactly those complete input strings ending in the suffix zero one. One student draws a three-state deterministic automaton but marks a state accepting as soon as zero one appears anywhere, and never leaves that accepting state. Another student tests only the string zero one and concludes that the design is correct. The teacher asks the team to separate the specification, transition model and evidence. They must process the entire input, show the state after each symbol and provide both an accepting example and a counterexample to the proposed design. No programming-language regular-expression extensions are assumed.
1. Why does the test 010 distinguish the proposed design from the required language?
Read the worked answer
The proposed sticky accepting state remembers that 01 occurred somewhere and therefore accepts 010. The required suffix language rejects it because the complete string ends in10, not01. A positive example alone did not distinguish these specifications.
2. Describe sufficient three-state information for the intended suffix automaton.
Read the worked answer
Track no relevant suffix, a final0, or a final01. From the final01 state, a0 moves to the final0 state and a1 to no relevant suffix. Only final01 is accepting after the complete string. This tracks the useful suffix rather than permanent historical occurrence.