2002 · 66 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesRegular LanguagesTime ComplexityComplexityComputational Complexity Of LanguagesDeterministic Finite AutomataFinite Automata TheoryNondeterministic Finite AutomataState Complexity
The upper bound for the state complexity of the shuffle of two regular languages is $2^{mn}-1$. We prove that this bound can be reached for some (not necessarily complete) deterministic finite automata With, respectively, $m$ and $n$ states. Our construction uses an alphabet of size 5.