Number of states of finite automata

[mathmari]

Hey!

Prove that for each $n>0$, a language $B_n$ exists where

1. $B_n$ is recognizable by an NFA that has $n$ states, and
   
2. If $B_n=A_1 \cup \dots \cup A_k$, for regular languages $A_i$, then at least one of the $A_i$ requires a DFA with exponentially many states.

Could you give me some hints how I could show that?? (Wondering)

 

[Valkarie]

Proof by induction: Base case ($n = 1$): Let $B_1 = A_1 \cup A_2$ where $A_1$ and $A_2$ are regular languages. Since $B_1$ can be recognized by an NFA with one state, then $A_1$ and $A_2$ have to be recognized by DFAs with at most one state. This implies that at least one of the $A_i$ requires a DFA with exponentially many states. Induction Hypothesis: Assume that for some $n > 0$, the statement is true for all $B_n$. Inductive Step: Let $B_{n+1} = A_1 \cup \dots \cup A_k$ where $A_i$ are regular languages. We know that $B_{n+1}$ can be recognized by an NFA with $(n+1)$ states. Therefore, each $A_i$ must be recognized by a DFA with at most $(n+1)$ states. But since the induction hypothesis holds for $n$, then we know that at least one of the $A_i$ requires a DFA with exponentially many states. Thus, for each $n>0$, a language $B_n$ exists where $B_n$ is recognizable by an NFA that has $n$ states, and if $B_n=A_1 \cup \dots \cup A_k$, for regular languages $A_i$, then at least one of the $A_i$ requires a DFA with exponentially many states.