77 votes 77 votes Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: $$\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$b$} \\\hline \llap{\rightarrow }\;{ q_0} & \text{$\{q_2\}$} & \text{$\{q_1\}$} & \text{$\{q_0\}$} \\\hline \text{$q_1$} & \text{$\{q_2\}$} & \text{$\{q_2\}$} & \text{$\{q_3\}$} \\\hline \text{$q_2$} & \text{$\{q_0\}$} & \text{$\emptyset$} & \text{$\emptyset$} \\\hline \quad\text{$q_3$}\quad & \text{$\emptyset$} & \text{$\emptyset$} & \text{$\{q_2\}$} \\\hline \end{array}$$ Then $\widehat{\delta}(q_2, aba)$ is $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$ Theory of Computation gatecse-2017-set2 theory-of-computation finite-automata + – Arjun asked Feb 14, 2017 edited Apr 14, 2019 by Pooja Khatri Arjun 28.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Puja Mishra commented Jan 14, 2018 reply Follow Share How this thing works ..... Refer Peter Linz ... 10 votes 10 votes vaibhav101 commented Feb 3, 2018 reply Follow Share This is better explained by $\epsilon$-closure in Compiler Design by Ullman 2 votes 2 votes Ray Tomlinson commented Jan 30 reply Follow Share First Make The Epsilon NFA then try to solve this question by taking $E-Clousure$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 140 votes 140 votes Starting state $: q_2$ and input string is "$aba$" $\text{Step 1: }$ Find Epsilon closure of $q_2 = \{q_2,q_0\}$ $\text{Step 2: }$ Find transitions on $a:$ $q_0\to q_1$ $q_2 \to \emptyset$ $\text{Step 3: }$ Find epsilon closure of $q_1= \{q_1,q_2,q_0\}$ $\text{Step 4: }$ Find transitions on $b:$ $q_1\to q_3$ $q_0\to q_0$ $q_2\to \emptyset$ $\text{Step 5:}$ Find epsilon closure of $q_0=\{q_0,q_2\}$ UNION epsilon closure of $q_3=\{q_3\}, = \{q_0,q_2,q_3\}$ $\text{Step 6:}$ Find transitions on $a:$ $q_0 \to q_1$ $q_2 \to \emptyset$ $q_3 \to \emptyset$ $\text{Step 7:}$ Find epsilon closure of $q_1: \{q_1,q_0,q_2\}$ Therefore answer is C. kapilthukral94 answered Feb 15, 2017 edited Apr 21, 2019 by Arjun kapilthukral94 comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments SushB commented Dec 26, 2020 reply Follow Share So ,sir we have to consider only those states which are used as epsilon move with string aba? @Arjun 0 votes 0 votes niha42 commented Jan 22, 2021 reply Follow Share What does extended transition function mean? 0 votes 0 votes kiioo commented Jan 22, 2021 reply Follow Share extended transition function gives the state the Automaton reaches after processing a string like aba. 2 votes 2 votes Please log in or register to add a comment.
38 votes 38 votes the transition is nothing but (((Q2,a),b),a) now applying Q2,a we go to Q0 but as lamda transition is there so it will also go to Q2 so now {(Q0,Q2),b} = Q0,Q2 now{(Q0,,Q2),a}=Q0,Q1,Q2 so C should be correct answer here Aboveallplayer answered Feb 14, 2017 Aboveallplayer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Sona Barman commented Jul 29, 2017 reply Follow Share Nice explanation. 0 votes 0 votes dattasai commented Sep 26, 2018 reply Follow Share @ Aboveallplayer Applying (Q2 on 'a') wont go to the state Q0 as there is no transition from Q2 on a 2 votes 2 votes Hirak commented Mar 25, 2019 reply Follow Share "now applying Q2,a we go to Q0 but as lamda transition is there so it will also go to Q2 " The above line is as wrong as any object can get... please dont provide such below grade answers.. and god knows why u gote so many upvotes.. Peace! 0 votes 0 votes Please log in or register to add a comment.
31 votes 31 votes Right answer is option C. Mostafize Mondal answered Oct 21, 2018 Mostafize Mondal comment Share Follow See 1 comment See all 1 1 comment reply shadymademe commented Aug 6, 2023 reply Follow Share The epsilon closure of any state must contain that state so after reading the $a$ and $b$, the epsilon closure of $q_3$ must by $\{q_3\}$ 0 votes 0 votes Please log in or register to add a comment.
29 votes 29 votes C is the answer. Prashant. answered Feb 14, 2017 edited May 6, 2019 by Pooja Khatri Prashant. comment Share Follow See all 19 Comments See all 19 19 Comments reply iarnav commented Aug 24, 2017 reply Follow Share @2018 @Prashant what will be the final states in this epsilon NFA? Can we say q0 and q2 b/c directly on seeing epsilon we are reaching them? 0 votes 0 votes Prashant. commented Aug 25, 2017 reply Follow Share see here no need of the final state since it is asking reachable states but not acceptable. But in question q2 is given as final. 2 votes 2 votes Sahil1994 commented Sep 5, 2017 i edited by Sahil1994 Sep 6, 2017 reply Follow Share Hi sir @Prashant @Bikram I made a transition diagram same as yours but i am not able to trace out the transition δˆ(q2,aba) .Can you please help me out in this. 0 votes 0 votes vijay_jr commented Dec 19, 2017 reply Follow Share $Transition : \varepsilon a\varepsilon \varepsilon ba$ 5 votes 5 votes jatin khachane 1 commented Oct 7, 2018 i edited by jatin khachane 1 Dec 1, 2018 reply Follow Share @Prashant Sir, EDIT needed: 1 } In question Why q2 is in set notation form in left column , is state q2 and {q2} are same ?? Is this approach correct ? Better alternative appraoch plz reply PETER LINZ For an nfa, the extended transition function is defined so that ∂*(qi,w) contains qj if and only if there is a walk in the transition graph from qi to qj labeled w. This holds for all qi, qj ∈ Q and w∈S q2 to q2 labeled walk => ∈a∈∈ba∈ q2 to q1 labeled walk => ∈a∈∈ba q2 to q0 labeled walk => ∈a∈∈ba∈∈ q2 to q3 no such walk ∂*(q2,aba) = {q0,q1,q2} 1 votes 1 votes Shaik Masthan commented Dec 3, 2018 reply Follow Share @jatin In question Why q2 is in set notation form in left column , is state q2 and {q2} are same ?? yes.. those are same... Moreover what you did according to the approach mentioned by peter linz book is also correct. 0 votes 0 votes srestha commented Dec 14, 2018 reply Follow Share @jatin @Shaik in $\epsilon$ closure transition on $\epsilon$ and alpbabet comes in any order Am I right? I mean in transition, it is no need to mentain transition on 'a' first and then $\epsilon$ transition right? 0 votes 0 votes Shaik Masthan commented Dec 14, 2018 reply Follow Share no mam... first you have to go on epsilon closure then you have to apply a on that set ! if you take alphabet first it will reach Q$_j$ on that you take epsilon closure it is equivalent to taking epsilon closure of Q$_j$ 2 votes 2 votes jatin khachane 1 commented Dec 14, 2018 reply Follow Share Yes...there should a walk from one state to other containing 'a' + any number of epsilon 0 votes 0 votes srestha commented Dec 14, 2018 reply Follow Share @jatin if a + any number epsilon then how epsilon comes first? @Shaik in epsilon transition , epsilon always comes first? Is it true for all other cases too? 0 votes 0 votes srestha commented Dec 14, 2018 reply Follow Share @Shaik if you take alphabet first it will reach Qj on that you take epsilon closure it is equivalent to taking epsilon closure of Qj plz elaborate more 0 votes 0 votes Shaik Masthan commented Dec 14, 2018 reply Follow Share .... 1 votes 1 votes jatin khachane 1 commented Dec 14, 2018 reply Follow Share @Shaik $\delta ^{*}\left ( Q0,a \right )$ ==> $\epsilon$ closure of Q0 ==> Transition on a==>$\epsilon$ closure of set obtained Isn't it is same as ==> Set of states reachable from Q0 on seeing any number of $\epsilon$ +'a' + any number of $\epsilon$ 0 votes 0 votes Shaik Masthan commented Dec 14, 2018 reply Follow Share reachable from Q0 on seeing any number of ϵ +'a' + any number of ϵ ϵ . 'a' . any number of ϵ 0 votes 0 votes jatin khachane 1 commented Dec 14, 2018 reply Follow Share Ya string concatenation i mean to say :) 0 votes 0 votes srestha commented Dec 14, 2018 reply Follow Share But peter linz says 1. First compute transition on input 2. Next $\epsilon$ close to the members computed 0 votes 0 votes Shaik Masthan commented Dec 14, 2018 reply Follow Share mam, in which context it is written, is important ! 0 votes 0 votes habedo007 commented Jan 7, 2020 reply Follow Share There is a walk between q2 to q3 like this: $\epsilon a b b$ Am I right? 0 votes 0 votes mohit7891 commented Jan 11 reply Follow Share bhai maja aa gya!! dhanyabad. glad to see such elegant,nice answer 0 votes 0 votes Please log in or register to add a comment.