Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, should be eliminated right?

enter image description here

UPDATE: My solution to the question in the comment

enter image description here

  • The "dead state" cannot be eliminated because we need to fill in a transition from $q$ on $b$. If we don't put in a dead state, like the last option, it will accept the string "bba" while the original DFA doesn't. The other option B can be eliminated as it doesn't accept "ba" while the original one does. – Gokul Nov 9 at 7:59
  • This DFA accepts all languages (over $\{a,b\}$ alphabet) except $bb\{a, b\}^*$. So, you can't get rid of $r$. If $r$ was an dead state too, then the minimal DFA would be one-state. – rus9384 Nov 9 at 11:19
  • @rus9384 okay...thanks . Is the elimination of the dead state mentioned in this problem correct . ibb.co/iav4QA – techno Nov 9 at 17:16
  • A is correct, D is not, D accepts all languages except $b^*$. It is not minimal either, $p$ and $q$ can be merged in one state. – rus9384 Nov 9 at 17:21
  • @rus9384 why? 1 and 5 can be combined into a single state as they have identical transitions . – techno 16 hours ago

enter image description here

The given dfa (d) will be formed. As far as your question about removal of state r: it can't be removed because state q is having transition to state r on input b. This is necessary because a dfa cannot leave any input transition, that is, it must define all the transitions for each and every state and for each and every input given to those states.

New contributor
Shubham Singh Manhas is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • Thanks a lot for solving the question.But if you cannot eliminate dead state with moves to it why is 4 eliminated here ibb.co/iav4QA – techno Nov 9 at 9:59
  • @techno in the link that you provided, the answer in the option in (b) don't even seems like a dfa to me. The states 3 and 2 don't have transitions defined for inputs b and a respectively. – Shubham Singh Manhas Nov 10 at 14:11
  • hmm strange its from GATE 2019 book by Pearson.. – techno 16 hours ago
  • Please see the update... is this a correct solution to the question in the comment. – techno 16 hours ago

There are two ways to define DFAs. In the more common way, for each state $q$ and symbol $\sigma$ there is exactly one edge exiting $q$ and labeled $\sigma$. In the lest common way, there is at most one such edge.

If you are using the second convention, then you are right that the dead state is not needed. But when using the first convention, dead states are necessary. Indeed, what should the automaton do upon reading $bb$? Any word starting $bb$ should be rejected, but the automaton has to reach some state upon reading $bb$; this is the dead state.

  • So... is the answer right? Please see my comment for the answer above... – techno Nov 9 at 10:01
  • The answer depends on which of the two definitions of DFA you use. Only you can tell. – Yuval Filmus Nov 9 at 15:09

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.