What is a dead state in automata?

By: Prof. Dr. Fazal Rehman | Last updated: February 3, 2024

What is a dead state in FA(DFA)?

We need to start a machine (DFA) to read a string. If machine reached successfully till its final string accepting state, then we say that string is accepted by our machine

But if we reach on a state where machine can’t move further to its final state, then this state is called dead state. Dead state is also known as dummy state.

Example of dead state

In this example, machine will be start, then if we want to read strings that are starting with a then machine can reach to its final state to accept a string.

But if we start machine with b, then machine can’t move further to final state. After reading b we are moving to the dead state.

Conclusion:

Machine is at dead state, so string is not acceptable by machine.

Note:

• Dead state may be required in DFA.
• Dead state is not required in NFA.

Why Dead state is not required in NFA?

Compare these two diagrams.

DFA for regular expression of a(a+b)*

 

NFA for regular expression of a(a+b)*

 

Note: DFA have only one transition of each alphabet from a state but NFA can have many transitions of one alphabet from a state. You can imagine that why dead state is not required in NFA because we have multiple ways to move to the final state.

List of 100+ Important Deterministic Finite Automata

Finite Automata Exercise Solution

Here I am showing you a list of some more important Deterministic Finite Automata used in the theory of automata and theory of computation.

1. DFA for  (a+b)* (a+b)a .
2. DFA for (bb)*(aa)* .
3. DFA for  b+a(a+b)*+a.
4. DFA for (a+b)*b+(bb)*a.
5. DFA for bb+a(a+b)*+aa.
6. DFA for  a(a+b)*+bb(a)* .
7. DFA for  a(a+b)b*+bb(a)*.
8. DFA for  b(aa)*a+a(bb)*b.
9. DFA for a+a(aa+b)*(aa)b.
10. DFA for a+a(aa+b)*+(aa)b.
11. DFA for (a+b)b(a+b)*+(aa)*b.
12. FA for strings starting with a and ending with a.
13. FA for the language of all those strings starting with a.
14. FA for the language of all those strings containing aa as a substring.
15. DFA for the language of all those strings starting and ending with the same letters.
16. DFA for the language of all those strings starting and ending with different letters.
17. DFA for the language of all those strings having double 0 or double 1.
18. DFA for the language of all those strings starting and ending with b.
19. DFA for ending with b.
20. DFA for the string of even A’s and even b’s.
21. DFA for the regular expression of  a(a+b)*+(bb)+a(ba)*+aba+bb*(a+b)*.
22. RegExp and DFA for strings having triple a’s or triple b’s.