Re: fsa: compleixity and frequency
- From: "Keith Ramsay" <kramsay@xxxxxxx>
- Date: 28 Jun 2005 05:44:06 -0700
John R W Woodward wrote:
|Suppose we list all the finite state automata (FSA) up to a
|certain size. The size of a FSA is the number of states in
|an automata. Many of the FSA can be shown to be equivalent
|(i.e. there are many FSA which accept a given language).
|
|Let us define the complexity of a language as the size of
|the smallest FSA that accepts that language and only that
|language.
|
|My hypothesis is that, a less complex language will have many
|FSA that can recognize it than a more complex language. In
|other words, a complex language will not be represented very
|frequently in the list of FSA up to a certain size. And a
|simple language will be represented more frequently.
|
|Is there any work on this?
(I redid the word-wrap on that to keep Google from breaking
up lines.)
Given a language L and a string s, there is the notion of
the prefix language P_s={t : st is in L}. For each state in
an automaton, there is the notion of the language accepted
at that state, consisting of those t that would be accepted
if we started the automaton in that state. If an automaton
accepts L, each accessible state accepts one of the P_s,
for if we can get to a given state by feeding the machine
a string s, then the strings t accepted starting at that
state have to be the strings in the prefix language
associated with s. Obviously if P_s1 <> P_s2, the states we
reach with s1 and s2 have to be distinct.
This gives us a criterion for an automaton accepting L.
It has to be possible to assign to each state of L one of
the P_s (or mark it as inaccessible) in a way compatible
with the transitions of the automaton. That is, if state
d1 goes to state d2 under the letter c, and we've associated
P_s with d1, then d2 has to be associated with P_{s+c}. The
assignment is unique: each state has to correspond to the
language accepted by it.
This shows us for one thing what the minimal automaton is;
it has one state for each distinct P_s. This is all standard
stuff.
It also turns the question of how many automata with n states
into a combinatorial problem. How many automata are there
that have such a way of partitioning their states? For
example, consider the language L in the alphabet {0,1}
consisting of those strings with an even number of 0s. The
prefix languages are just L and L', the set of strings with
an odd number of 0s. So the number of automata with n states
that recognize this language is equal to the sum over all
ways of partitioning an n-element set into three subsets
A,B,C, of the number of ways of assigning transitions between
them compatible with the original. In this case, if the
partition is into A,B,C, each state in A has to go to a state
in B under 0, and to some state in A under 0; each state in
B has to go to a state in A under 0 and to a state in B under
1. The states in C are irrelevant (inaccessible). So the
number of transitions compatible with the partition is
(|B|^|A|)*(|A|^|A|)*(|A|^|B|)*(|B|^|B|)*(n^2|C|)
out of n^(2n) possible, where |A| is the number of elements
of the set A.
I'm assuming that somewhere this has been worked out before,
but maybe it's simple enough to work out ourselves. It seems
like the rate of growth of the number of equivalent automata
with n states depends on not just the number of states in
the minimal automaton, but on how they're connected together.
This will have some relationship with how many there are,
but I'm not sure how close a relationship.
Keith Ramsay
.
- References:
- fsa: compleixity and frequency
- From: John R W Woodward
- fsa: compleixity and frequency
- Prev by Date: Re: time complexity
- Next by Date: Re: ZFC
- Previous by thread: fsa: compleixity and frequency
- Next by thread: CfP : Workshop on Model Design and Validation (MoDeVa) at Models
- Index(es):
Relevant Pages
|
Loading
