edited by
28,051 views
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

  1. $\emptyset$
  2. $\{q_0, q_1, q_3\}$
  3. $\{q_0, q_1, q_2\}$
  4. $\{q_0, q_2, q_3 \}$
edited by

12 Answers

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.

edited by
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

31 votes
31 votes

Right answer is option C.

 

29 votes
29 votes

C is the answer.

edited by
Answer:

Related questions