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.1k 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 Show 16 previous comments 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.