patternMinor
Finding the upper bound of states in Minimal Deterministic Finite Automata
Viewed 0 times
theboundfinitestatesautomatadeterministicfindingminimalupper
Problem
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.
The way I am trying to solve the problem:
Am I right?
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.
The way I am trying to solve the problem:
- $ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
- Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.
Am I right?
Solution
This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of
$$2^{nm}. $$
This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound
$$ n2^m. $$
This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^ \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.
You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^$ with $(\Sigma^n)^$.
$$2^{nm}. $$
This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound
$$ n2^m. $$
This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^ \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.
You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^$ with $(\Sigma^n)^$.
Context
StackExchange Computer Science Q#126648, answer score: 3
Revisions (0)
No revisions yet.