Mixing
Minimizing DFA - Dead state elimination
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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?
formal-languages automata finite-automata
asked 3 hours ago
techno
11418
add a comment |
up vote
1
down vote
favorite
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?
formal-languages automata finite-automata
asked 3 hours ago
techno
11418
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
2 hours ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
formal-languages automata finite-automata
asked 3 hours ago
techno
11418
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?
formal-languages automata finite-automata
formal-languages automata finite-automata
asked 3 hours ago
techno
11418
asked 3 hours ago
techno
11418
asked 3 hours ago
techno
11418
asked 3 hours ago
techno
11418
asked 3 hours ago
techno
11418
11418
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
2 hours ago
add a comment |
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
2 hours ago
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
2 hours ago
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
2 hours ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
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.
answered 2 hours ago
Shubham Singh Manhas
212
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
26 mins ago
add a comment |
up vote
0
down vote
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.
answered 2 hours ago
Yuval Filmus
186k12176337
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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.
answered 2 hours ago
Shubham Singh Manhas
212
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
26 mins ago
add a comment |
up vote
2
down vote
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.
answered 2 hours ago
Shubham Singh Manhas
212
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
26 mins ago
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
answered 2 hours ago
Shubham Singh Manhas
212
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.
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.
answered 2 hours ago
Shubham Singh Manhas
212
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.
answered 2 hours ago
Shubham Singh Manhas
212
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.
answered 2 hours ago
Shubham Singh Manhas
212
answered 2 hours ago
Shubham Singh Manhas
212
212
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.
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.
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
26 mins ago
add a comment |
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
26 mins ago
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
26 mins ago
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
26 mins ago
add a comment |
up vote
0
down vote
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.
answered 2 hours ago
Yuval Filmus
186k12176337
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
add a comment |
up vote
0
down vote
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.
answered 2 hours ago
Yuval Filmus
186k12176337
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
add a comment |
up vote
0
down vote
up vote
0
down vote
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.
answered 2 hours ago
Yuval Filmus
186k12176337
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.
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
186k12176337
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
add a comment |
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
So... is the answer right? Please see my comment for the answer above...
– techno
24 mins ago
add a comment |
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99799%2fminimizing-dfa-dead-state-elimination%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
2 hours ago