Strings & Automata

Work fresh traces, diagnose invalid implementations, and identify model boundaries.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. KMP prefix-function values for "ababaca" end in what value?

2. KMP matches "abab" and then mismatches the next character. What is the purpose of falling back through the prefix table?

Select one answer.

Skip all future occurrences of the mismatching letter Restart the text scan from index zero Assume the full pattern matched Reuse a matched suffix that is also a pattern prefix

3. Under full-match regex semantics with . and *, does pattern a*b match "aaabx"?

Select one answer.

Only when the text is ASCII Yes, finding a prefix is enough Yes, * consumes every remaining character No, x remains unmatched

4. Under full-match semantics, how many copies of a may a* consume when matching the empty string?

5. A numeric FSM has read "12e-" at end of input. What is the correct decision?

Select one answer.

Accept because 12 was already valid Remove the exponent silently Accept because a sign completes an exponent Reject because the exponent lacks digits

6. Two search engines evaluate a|ab on "ab" from the same leftmost start. A leftmost-first engine selects a. A POSIX leftmost-longest engine selects which match?

Select one answer.

The empty string ab No match a

7. Why can memoizing (text position, pattern position) help a restricted regex matcher with nested alternatives?

Select one answer.

It prevents reevaluating identical suffix subproblems It removes the need to test accepting states It makes backreferences finite-state It changes full matches into substring matches

Auto-advance on pass

Join Discord