The Complexity of Languages Resulting from the Concatenation Operation
Abstract
We prove that for all m, n, and α
with 1≤α≤f(m,n)
, where f(m, n) is the state complexity of the concatenation operation, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet Σ
with |Σ|≤2n+4
, such that the minimal DFA for the language L(A)L(B) has exactly α
states. This improves a similar result in the literature that uses an exponential alphabet.
Domains
Origin | Files produced by the author(s) |
---|
Loading...