Question

Prove that for each $\mathbf{n}\mathbf{>}\mathbf{0}$, a language${\mathbf{B}}_{\mathbf{n}}$ exists where

1. ${\mathbf{B}}_{\mathbf{n}}$is recognizable by an NFA that has$\mathbf{n}$ states, and
2. If ${\mathbf{B}}_{\mathbf{n}}\mathbf{=}{\mathbf{A}}_{\mathbf{1}}\mathbf{\cup }\mathbf{\dots }\mathbf{\cup }{\mathbf{A}}_{\mathbf{k}}$, for regular languages ${\mathbf{A}}_{\mathbf{i}}$, then at least one of the${\mathbf{A}}_{\mathbf{i}}$ requires a DFA with exponentially many states.

Short answer

1. ${\mathrm{B}}_{\mathrm{n}}$is recognizable by an NFA that has $\mathrm{n}$states.
2. Yes, for ${\mathrm{B}}_{\mathrm{n}}={\mathrm{A}}_1\cup \dots \cup {\mathrm{A}}_{\mathrm{k}}$, for regular languages ${\mathrm{A}}_{\mathrm{i}}$, then at least one of the${\mathrm{A}}_{\mathrm{i}}$ requires a DFA with exponentially many states.

Step-by-step solution

Explain DFA.

Deterministic Finite Automata is the computer model that has the definite next state. Nondeterministic Finite Automata has the several states, one of them can be the next state.

Step 2:Prove that the given language is recognizable by an NFA.

a.

Consider the given language ${\mathrm{B}}_{\mathrm{n}}$, for each $\mathrm{n}>0$. Assume that $\mathrm{n}=1$, then ${\mathrm{B}}_{\mathrm{n}}=\{\mathrm{\epsilon },0,1\}$. The NFA for the language $\mathrm{N}=(\left\{{\mathrm{q}}_0\right\},\sum ,\mathrm{\delta },{\mathrm{q}}_0,\left\{{\mathrm{q}}_0\right\})$, wit single state that accepts,$\mathrm{\delta }({\mathrm{q}}_0,\mathrm{\epsilon }\left|0\right|1)={\mathrm{q}}_0$.

Consider that the given language can be divided into two regular expressions $\mathrm{E}$, and${\mathrm{E}}^{\text{'}}$ of length${\mathrm{n}}_1,{\mathrm{n}}_2<\mathrm{n}$ and${\mathrm{n}}_1+{\mathrm{n}}_2=\mathrm{n}$ .

By inductive hypothesis, it can be concluded that the NFA is accepting the regular expressions , $\mathrm{E}$and$E\text{'}$ , consist of at least ${\mathrm{n}}_1$and$n_2$ states. It has been known that the set of regular expression is closure under Union.

Therefore, the language $B_n$is recognizable by an NFA that has $n$states.

Prove that the given regular languages require a DFA with exponentially many states

b.

Consider the ${\mathrm{B}}_{\mathrm{n}}={\mathrm{A}}_1\cup \dots \cup {\mathrm{A}}_{\mathrm{k}}$, where${\mathrm{A}}_{\mathrm{i}}$ is a regular. Construct the DFA equivalent to the given NFA, there exist at least$\mathrm{n}$ and at most$2^{\mathrm{n}}$ states. For all the regular languages, there exists a equivalent DFA. By the pigeon hole principle, it can be stated that one DFA requires,$2^{\mathrm{i}}$ states to recognize a language.

Therefore, Yes, for ${\mathrm{B}}_{\mathrm{n}}={\mathrm{A}}_1\cup \dots \cup {\mathrm{A}}_{\mathrm{k}}$, for regular languages ${\mathrm{A}}_{\mathrm{i}}$, then at least one of the ${\mathrm{A}}_{\mathrm{i}}$requires a DFA with exponentially many states.