Furthermore, any FA can be effectively turned into a deterministic FA accepting the same language.
this paper will assume that FAs are deterministic, although technically, unambiguity is sufficient for our constructions to apply.