7.5k views

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 | 7.5k views
+6

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

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

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

edited by
+1
Best explanation for this question.
0
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
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.

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

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

Whats Wrong in this ?
0
What is "do nothing" transition?
after using 'a' and 'b' as input, you either have to use 'epsilon' or 'a' to make the transition
+9
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

0
Nice explanation.
+2

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

0

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

by Veteran
edited
0

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

+2
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.
0

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.

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

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}
0

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

@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

+1

....

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

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

ϵ . 'a' . any number of ϵ

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

1. First compute transition on input

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

Am I right?

so ans is C

by Loyal
+1
I'm not getting C, I'm getting A...explain plz!
+13
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

q0------------->q0

q2------------>'phi'

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

q2------------>'phi'

q3----------->'phi'

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

0
Best explantation so far.
+1
very well explained. Thanx
0

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

0
thanks
+7

Thankyou so much.I did the same way 😊

0

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

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

this formula works here ????
0
Yes

### Right answer is option C.

by Active

Let's see this one....

by Active

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

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