- For any problem, if the answer is yes or no, then that problem is known as a decision problem otherwise it is an optimization problem.
- For any problem, if the algorithm is possible to solve that problem, then it is decidable problem.
There are three problems in Finite Automata
- Emptiness Problem
- Finiteness Problem
- Equivalence Problem
Emptiness Problem
The emptiness problem in Finite Automata is to decide whether the given automata are accepting empty language or not.
There is an Algorithm available to check the emptiness of Finite Automata.
- Step 1: Select those states which are not reachable from the initial state, delete those states and transitions. Using DFS or BFS.
- Step 2: In the remaining Finite Automata, if at least one final state then it is accepting non-empty language otherwise empty language.
Conclusion: The emptiness problem of finite automata is decidable and decision problem.
Example: Consider a Finite Automata
Given FA is accepting empty language. There is no final state in reachable states.
Finiteness Problem
The finiteness problem in Finite Automata is to decide whether the given automata is accepting finite language or infinite language.
There is an Algorithm available to check the finiteness of Finite Automata.
- Step 1: Select those states which are not reachable from the initial state, delete those states and transitions. Using DFS or BFS.
- Step 2: In the remaining Finite Automata, if any state from which we cannot reach the final state, delete those states and transitions.
- Step 3: In the remaining Finite Automata, if at least one cycle is available then it is accepting infinite language otherwise finite language.
Conclusion: The finiteness problem of finite automata is decidable and decision problem.
Example: Consider a Finite Automata
After applying the first 2 steps the resultant Finite Automata is
Loops exist in the resultant finite automata, hence accepting infinite language.
Equivalence Problem
The equivalence problem in Finite Automata is to decide whether the given two automata are accepting the same language or not.
There is an Algorithm available to check the equivalence of given two Finite Automata.
- Step 1: Create a transition table for given FAs.
- Step 2: If any entry of the table contains the final state of one automaton and the non-final state of other automata then the given FAs are not accepting the same language.
Conclusion: The equivalence problem of finite automata is decidable and decision problem.
Example: Consider the following two Finite Automata
The transition table for the above two automata is
Transition table entries are in form of (A, B), where A is the state from Finite Automata 1 and B is the state from Finite Automata 2.
NF means Non-Final State
F means Final State
Above transition table does not contain any conflicting entry hence the given FAs are accepting the same language.
