29 votes 29 votes Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$ Theory of Computation gatecse-2014-set1 theory-of-computation finite-automata easy + – go_editor asked Sep 26, 2014 edited May 1, 2019 by Pooja Khatri go_editor 14.8k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply vaibhavkedia968 commented Jan 22, 2020 reply Follow Share What is meant by "reachable" over here? Set of terminating states for the string 0011 or set of all the states that can be visited by 0011? For eg, if q2 was the only state where 0011 could terminate, then the answer will be {q2} or {q0,q1,q2}? 0 votes 0 votes raja11sep commented Dec 21, 2021 reply Follow Share Extended transition function. 0 votes 0 votes theradash commented Jan 10 reply Follow Share Extended transition function from state q0 on string 0011. 0 votes 0 votes Please log in or register to add a comment.
Best answer 45 votes 45 votes $q_0, q_1$ and $q_2$ are reachable from $q_0$ on input $0011$ Correct Answer: $A$ Praveen Saini answered Mar 4, 2015 edited May 9, 2021 by gatecse Praveen Saini comment Share Follow See all 13 Comments See all 13 13 Comments reply Regina Phalange commented Apr 12, 2017 reply Follow Share @Praveen Saini Can't we move like this q0,q0,q0,q1 because q0 has both 0,1 inputs 0 votes 0 votes shraddha_gami commented Apr 13, 2017 reply Follow Share @ Divya Bharti It is NFA. So, if we consider for all possibility then answer is q0,q1,q2 1 votes 1 votes iarnav commented Aug 23, 2017 reply Follow Share @Praveen Saini Sir, can we also convert it to DFA and check, well, I did convert to DFA and found out that string 0011 end up in state {q0 q1 q2} I just want to confirm can we convert NFA to DFA and check it? 1 votes 1 votes Praveen Saini commented Aug 24, 2017 reply Follow Share yes it will work fine. 1 votes 1 votes Mayankprakash commented Jul 14, 2018 reply Follow Share @praveen 1.How to tackle this type of problem. 2.why not Q3 is considered as it is the final state as any string accepted by automata must end up at final state. Please suggest Thanks 0 votes 0 votes Praveen Saini commented Aug 7, 2018 reply Follow Share Question is not about accept and reject of input 2 votes 2 votes Shamim Ahmed commented Oct 22, 2018 reply Follow Share @Mr. Praveen, Can you please justify why we should not reach the final state? Isn't it mandatory to reach final state for a given input string? I'm in doubt... 0 votes 0 votes Ayush Upadhyaya commented Jan 2, 2019 reply Follow Share $\delta^*(q,w)=$contains only those states which have a walk from state q labelled w. 0 votes 0 votes sridhar15399 commented Dec 19, 2019 reply Follow Share how to solve it fastly 0 votes 0 votes its_vv commented Aug 7, 2021 reply Follow Share What will be the ans when more than one options are correct ? 0 votes 0 votes ankit3009 commented Nov 17, 2021 reply Follow Share Options A and B both will be suitable then if asked for MSQ. 3 votes 3 votes raja11sep commented Dec 21, 2021 reply Follow Share @ankit3009 yes ankit. Question should be like “set of all reachable states” then only option A will be correct. 3 votes 3 votes Hira Thakur commented Jan 17 reply Follow Share Option $C,D$ are dummy options because we cannot reach to State $q_3$ 0 votes 0 votes Please log in or register to add a comment.
11 votes 11 votes qo,q1,q2 can be reached in this nfa by enumerating all the possibilities Bhagirathi answered Sep 26, 2014 edited Jan 14, 2018 by Puja Mishra Bhagirathi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0 {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1 {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2 Hence δ (q0, 0011) = {q0, q1, q2} varunrajarathnam answered Aug 15, 2020 edited Jan 17 by Hira Thakur varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0 {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1 {q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2 Hence δ (q0, 0011) = {q0, q1, q2} varunrajarathnam answered Aug 23, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.