Given two minimal deterministic finite automatons called A and B where A accepts the finite language L(A) and B accepts the finite language L(B) and the alphabet of both languages and automatons are Σ={0,1}.
This implies that |Σ|=2.
Because that both A and B are minimal, there is no possibility to remove any state and transition neither from A nor from B, so L(A) and L(B) are unchanged.
C is minimal deterministic finite automaton that accepts L(C), where L(C)=L(A)∩L(B)
This implies that L(C) is finite and their alphabet is Σ={0,1} as well.
Because that C is minimal if one of its states and transitions of C is removed then L(C)≠L(A)∩L(B) anymore.
Assume that |A| is the number of states of automaton A, |B| is the number of states of automaton B and |C| is the number of states of automaton C.
I already know that I can construct C as the product of A and B so L(C)=L(A)∩L(B), but then |C|=θ(|A|•|B|), but C is not necessarily m̲i̲n̲i̲m̲a̲l̲. The running time of the algorithm that constructs the product takes θ(|A|•|B|).
It is possible then to run Hopcroft's algorithm to minimize automaton C in running time of O(|C|•log(|C|)), so still L(C)=L(A)∩L(B) and after that |C|≤|A|•|B|.
Because that |C|=θ(|A|•|B|) before the minimization, then Hopcroft runs in:
O(|A|•|B|•log(|A|•|B|)).
So in total the running time to get the minimal automaton C, so L(C)=L(A)∩L(B) this way takes O(|A|•|B|•log(|A|•|B|)).
Let me know if there is more efficient, faster and better time complexity algorithm to achieve the same thing.
But my real question is what is the space of the minimal automaton C after all this?
I know that it is |C|=Ω(1) in the best case, when L(A)∩L(B)=∅, because minimal automaton that accepts the empty language, only needs one state, which is the starting state, not final and trap, i.e. the automaton remains in this state for each read character from the input tape.
In this case |QC|=1 ∧ |FC|=0 ∧ δC(q0C,0)=δC(q0C,1)=q0C
But of course that this case won't happen always, so I am asking what will be the largest space of automaton C in the worst case?
For sure |C|=O(|A|•|B|), but can it be any better?
I think that yes, i.e. |C|=O(|A|+|B|)
Because it is always true that |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)|, where |L(A)| is the cardinality of L(A) as a set of words/strings, |L(B)| is the cardinality of L(B) as a set of words/strings and |L(C)| is the cardinality of L(C) as a set of words/strings and |L(A)|, |L(B)| and |L(C)| are all finite natural numbers, because L(A), L(B) and L(C) are all finite sets of words/strings. So the cardinality of the language is the number of words/strings in that language as set of words/strings. So if |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)| then L(C) never has more words/strings than both L(A) and than L(B).
If L(C) is smaller language both than L(A) and L(B) and may have fewer/lesser words/strings, then the minimal automaton C doesn't need more states than the minimal automaton A and minimal automaton B, so I don't think that it is right that |C|=O(|A|•|B|) when A, B and C are minimal and L(C)=L(A)∩L(B), but what I said is not a proof.
I need a proof that this statement is correct or refutation that this statement is incorrect and wrong, but I don't know how to either prove it or refute it.
It should be noted that if minimal automaton C doesn't have more states than minimal automaton A and B then:
|C|≤|A| ∧ |C|≤|B| and thus |C|≤min(|A|,|B|).
Any help or directions?
EDIT: I have just found and discovered 1 hour ago that the length of each word in L(A) and L(B) are equal, i.e. ∀ w,x,y,z: w∈L(A) ∧ x∈L(A) ∧ y∈L(B) ∧ z∈L(B) then |w|=|x|=|y|=|z|, where |w| is the length of the word w, |x| is the length of the word x, |y| is the length of the word y and |z| is the length of the word z. Sorry that I didn't know this before.
I also want to know the relationship between |C| and (|A|,|B|) when |A|→∞ ∧ |B|→∞, i.e. both the number of states of automaton A and automaton B are going to infinity.
You don't have to delete anything, just edit your answers and insert html that shows that the claim remains true with the new assumption or it doesn't true with that assumption.