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.4k 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 sutanay3 commented Jun 18, 2018 reply Follow Share Best explanation for this question. 4 votes 4 votes SANDEEP1729 commented Jul 15, 2019 reply Follow Share Sir while converting from epsilon nfa to nfa why we are applying epsilon closure and state transition and epsilon closure. Please tell the reason for kt 0 votes 0 votes srestha commented Nov 18, 2019 reply Follow Share In this question, all state can be reached from $q_{2}$, but they are removing those states, which leads to reject state. So, $q_{3}$ has been removed. 0 votes 0 votes Adarsh Pandey commented Jun 21, 2020 reply Follow Share visually https://imgur.com/a/4iy1Q0n 6 votes 6 votes bthebestSelf commented Dec 10, 2020 reply Follow Share In step 3 how you include q0 in epsilon closure ? 0 votes 0 votes kiioo commented Dec 15, 2020 reply Follow Share q1 on $\varepsilon$ goes to q1 q1 on $\varepsilon$ goes to q2 q2 on $\varepsilon$ goes to q0 therefore $\varepsilon$ closure of q1 = {q0, q1, q2} 1 votes 1 votes 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.