  In this paper we define a new descriptional complexity measure for
Deterministic Finite Automata, BC-complexity, as an alternative to the state
complexity. We prove that for two DFAs with the same number of states
BC-complexity can differ exponentially. In some cases minimization of DFA can
lead to an exponential increase in BC-complexity, on the other hand
BC-complexity of DFAs with a large state space which are obtained by some
standard constructions (determinization of NFA, language operations), is
reasonably small. But our main result is the analogue of the "Shannon effect"
for finite automata: almost all DFAs with a fixed number of states have
BC-complexity that is close to the maximum.
