Finite Transducers and Nondeterministic State Complexityof Regular Languages

摘要

We obtain a sharp upper bound for the nondeterministic state complexity of the applica-tion of a finite transducer to a regular language.