Theory of Automata

Trap State vs. Dead State in TOC



Trap state is used in DFA while Dead State is found in NFA. Let see the comparison of trap state vs. dead state in TOC.

Trap State

Trap state considered the receiving inputs as rejected inputs. This concept is used in DFA. It is also known as trap configuration.

As we know in case of DFA, there must be a dedicated path for each input of Sigma. So, some of the inputs has to rejects according to requirement.

Example

Draw a DFA which accept only “aaab”.

Solution

As in following DFA, the current state is q0 and it change to q1 through input “a” but for input “b” it does not need  for self-loop. So, for input “b” transition goes to trap state (q3).

Trap state

Dead State

When there is no path exist  to reach at certain state then that state will be considered as dead state. It is used in NFA but cannot be used in DFA. It is also known as dead configuration.



Example

Look at the following DFA where q4 is dead state because there is not path exist to reach at q4.

Dead state

Note: If dead state is non-final then it can be removed without any problem from NFA graph

 

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest