Checking Understanding of DFA Regular Operations - Intersection and Star

Question

I'm currently taking a Logics course, and trying to understand the regular operations, intersection and star. I have a question regarding the work I have done so far.

Given the following information:

$L_A$ and $L_B$ are regular languages defined by DFAs $A$ and $B$. $N_A$ and $N_B$ are the number of states in DFAs $A$ and $B$.

What are the HIGHEST number of states one would need in DFAs for the languages

1. $L_A \cap L_B$
2. ${L_A}^*$ (star)

INTERSECTION operation

I have understood it so that the state of the new automaton A∩B will be the pairs of states in A and B. That is:

Na∩b = Na x Nb.

That is, the HIGHEST number of states needed in the DFA for language A∩B is the product of the number of states in A (Na) and B (Nb). Is this correct?

Another question: how does this number differ from the highest number of states in the CONCATENATION operation?

STAR operation:

For the star operation, I'm at a loss. Any advice on how I can approach this?

Answer 1

Your question is formally incorrect because you are using the same notation for a language and an automaton and also because your notation $Na \cap b$ is not clear at all. However, the meaning of your question is clear and the answer is known, but not easy. So let me first reformulate your question in a more rigorous way and then give the answer.

The (state) complexity of a regular language $L$ is the number of states $c(L)$ of its minimal DFA.

Question 1. Estimate $\max\{ c(L_1 \cap L_2) \mid c(L_1) = n_1 \text{ and } c(L_2) = n_2 \}$

Question 2. Estimate $\max\{ c(L_1L_2) \mid c(L_1) = n_1 \text{ and } c(L_2) = n_2 \}$

Question 3. Estimate $\max\{ c(L^*) \mid c(L) = n \}$

Answers.

\begin{align*} \max\{ c(L_1 \cap L_2) \mid c(L_1) = n_1 \text{ and } c(L_2) = n_2 \} &= n_1n_2\\ \max\{ c(L_1L_2) \mid c(L_1) = n_1 \text{ and } c(L_2) = n_2 \} &= n_12^{n_2} - 2^{n_2-1}\\ \max\{ c(L^*) \mid c(L) = n \} &= 2^{n-1}+2^{n-2} \end{align*} These results hold for languages over an alphabet containing at least two-letters (and even 3 letters for the product). For one-letter alphabet, the values are also known, but are different.

References

S. Yu, Regular languages, in Handbook of language theory, G. Rozenberg et A. Salomaa (ed.), vol. 1, ch. 2, pp. 679–746, Springer, 1997.

For related questions, I recommend reading the articles of H. Gruber, M. Holzer, M. Kutrib, H. Petersen, where you will find plenty of further references.

Answer 2

My naive estimates for the number of states needed:

Concatenation $L_A+L_B$ can be detected by "chaining" $A$ and $B$ automata, thus not more than $N_A+N_B$ states.

Intersection needs running $A$ and $B$ "simultaneously", thus using the product automaton with not more than $N_A N_B$ states.

The Kleene hull ${L_A}^* = L^0 \cup L \cup L^2 \cup \ldots$ would need finite repetition of $A$. We could extend it into a $\epsilon$-NFA with extra $\epsilon$-transitions from the final states to the initial state. The number of states would not increase. Turning this into a DFA would result in a DFA with up to $2^{N_A}$ states.

All those automata could be minimized, so lower upper bounds are possible.