The Gateway to Computer Science Excellence
+44 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 \}$
in Theory of Computation by Veteran
edited by | 7.5k views

How this thing works ..... Refer Peter Linz ...

This is better explained by $\epsilon$-closure in Compiler Design by Ullman

8 Answers

+68 votes
Best answer

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
Best explanation for this question.
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
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.
+32 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


so C should be correct answer here

by Boss
We can also reach q3 .... through Epsilon  Q0-> Q1(a)->Q3(b)->Q3(do nothing)

Whats Wrong in this ?
What is "do nothing" transition?
after using 'a' and 'b' as input, you either have to use 'epsilon' or 'a' to make the transition
Although the right answer is C, there are problems with the reasoning here. According to me, here is the right way:

States after input a -> q0, q1, q2

States after input b -> q0, q2, q3

States after input a -> q0, q1, q2

Therefore, answer (c)
Nice explanation.


Applying (Q2 on  'a') wont go to the state Q0 as there is no transition from Q2 on a


"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..


+26 votes

C is the answer.

by Veteran
edited by

@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?

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.

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.

$Transition : \varepsilon a\varepsilon \varepsilon ba$
@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


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}


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.

@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

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$
Yes...there should a walk from one state to other containing 'a' + any number of epsilon

if a + any number epsilon

then how epsilon comes first?


in epsilon transition , epsilon always comes first?

Is it true for all other cases too?



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 




$\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$

reachable from Q0 on seeing any number of ϵ +'a' + any number of ϵ

 ϵ . 'a' . any number of ϵ

Ya string concatenation i mean to say :)
But peter linz says

1. First compute transition on input

2. Next $\epsilon$ close to the members computed
mam, in which context it is written, is important !
There is a walk between q2 to q3 like this:
$\epsilon a b b$

Am I right?
+15 votes

so ans is C

by Loyal
I'm not getting C, I'm getting A...explain plz!
starting state : q2

step1: Find Epsilon closure of q2 = {q2,q0}

step2: Find transition on 'a' :     q0------------->q1

                                                   q2------------->'phi' (i.e nothing)

step3: Find epsilon closure of 'q1'= {q1,q2,q0}

step4: Find transition on 'b' :      q1------------->q3



step5: Find epsilon closure of 'q0' union 'q3':   epsilon closure of 'q0'={q0,q2} UNION  epsilon closure of 'q3'={q3}

step6: Find transition on 'a':  q0------------>q1



step7: Find epsilon closure of 'q1': {q1,q0,q2}


Threfore answer= C
Best explantation so far.
very well explained. Thanx

Hi @2018 ji,

First of all thank for giving good answer. But your answer requires small correction. For example there is no transaction from $(q_{3},a)$. So  $(q_{3},a) \neq \left \{ q_{3} \right \}$.


Thankyou so much.I did the same way 😊


For making above state transition function, this state transition diagram will help a lot.

$\delta (q_{2},aba) = \epsilon (\delta (\epsilon (q_{2}),aba))$

this formula works here ????
+15 votes

Right answer is option C.


by Active
+2 votes

Let's see this one....

by Active
0 votes

On giving the input "aba" to q2, where can we possibly go?

The answer will not contain q3, because to reach q3, we need to end with b strictly. But our input "aba" ends with a. B and C eliminated.

Answer is not ϕ because with just epsilon transitions, we'll go to at least some state from q2. Option A eliminated.

Hence, Option C

Solved it under a minute!

The proper solution would be to check where can we go from q2 on aba manually, as other answers show.


by Loyal
0 votes

I find Peter Linz's definition of the extended transition function $\delta^*$ for NFAs more intuitive and easy to use.

For an NFA, $\delta^*(q_i, w)$ (where w is a string in $\sum^*$) contains state $q_j$ if and only if there is a walk in the transition graph from $q_i$ to $q_j$ labelled w.

This walk can also have epsilon in it. In this NFA, the only way I see to cover $aba$ is $q_2 -> q_0 -> q_1 -> q_2 -> q_0 -> q_0 -> q_1$. So $q_1$ is definitely in $\delta^*(q_2, aba)$.

Now we can use epsilon transitions to go to $q_2$ and $q_0$ from $q_1$, which doesn't change the input string. So a walk exists to those states for input $aba$ as well. So all three of these states are part of the answer.

by Active
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,221 questions
59,854 answers
118,096 users