1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Gokul
    Nov 9, 2018 at 7:59
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Nov 9, 2018 at 11:19
  • $\begingroup$ @rus9384 okay...thanks . Is the elimination of the dead state mentioned in this problem correct . ibb.co/iav4QA $\endgroup$
    – techno
    Nov 9, 2018 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Nov 9, 2018 at 17:21
  • $\begingroup$ @rus9384 why? 1 and 5 can be combined into a single state as they have identical transitions . $\endgroup$
    – techno
    Nov 13, 2018 at 9:59

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – techno
    Nov 9, 2018 at 9:59
  • $\begingroup$ @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. $\endgroup$
    – SSM
    Nov 10, 2018 at 14:11
  • $\begingroup$ hmm strange its from GATE 2019 book by Pearson.. $\endgroup$
    – techno
    Nov 13, 2018 at 10:00
  • $\begingroup$ Please see the update... is this a correct solution to the question in the comment. $\endgroup$
    – techno
    Nov 13, 2018 at 10:06
  • $\begingroup$ @techno it seems correct to me, state 4 is the trap state and any input thereafter will be trapped in it. $\endgroup$
    – SSM
    Nov 14, 2018 at 11:43
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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