State Complexity of Unambiguous Operations on Deterministic Finite Automata
Abstract
The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn−1
; for the unambiguous concatenation, it is known to be m2n−1−2n−2
(Daley et al. “Orthogonal concatenation: Language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 382n+1
. In the case of a unary alphabet, disjoint union requires up to 12mn
states, unambiguous concatenation has state complexity m+n−2
, and unambiguous star requires n−2
states in the worst case.
Domains
Origin | Files produced by the author(s) |
---|
Loading...