This can be done according to its definition, and takes .
More clever versions can achieve .
This brings the total running time for FINITE-AUTOMATON-MATCHER to .
.
.
.
.
