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:
- $ L(A_1) \backslash L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2)$ , which is language, that is recognised by automata $ L’$ with $ n*m$ states
- Determinization of $ L’$ which has $ (n*m)^2$ states and it is the upper bound of states.
Am I right?