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.9k 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 Show 10 previous comments 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.