I just started to learn about Automata and I came across a problem I could not wrap my head around.
We let both A_1 and B_1 be regular languages defined by DFAs A and B. Let nA and nB be the number of states in A and B, respectively.
From this information, how can I find the highest number of states in DFAs for the languages A ∩ B and A∗, and the highest number of states in NFAs for the languages A ∩ B, AB and A∗
Thanks for any answers and tips
What you are asking about is very related to what is called state complexity. The corresponding article in wikipedia gives the complexity of many operations with references to the corresponding articles, which normally contain the examples proving these bounds.
Of course, you ask about "the highest number of states" not about the lowest number in the worst case, which is what state complexity describes. But this highest number only makes sense in a restricted setting. If I am allowed to construct whatever automaton I wish, I can construct automata with arbitrary numbers of states for any language. You would have to ask for the highest number of states for minimal automata, for example. Some of the articles also provide upper bounds of this kind.