The Gateway to Computer Science Excellence
+36 votes
6k 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 \}$
in Theory of Computation by Veteran (423k points)
edited by | 6k views
+6

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

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

7 Answers

+53 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.

by (475 points)
edited by
0
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.
+29 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

by Boss (17.9k points)
+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
+8
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)
0
Nice explanation.
+2

Aboveallplayer 

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!

+25 votes

C is the answer.

by Veteran (62.7k points)
edited by
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 ?

Better alternative appraoch plz reply

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 !
+15 votes

so ans is C

by Loyal (6.8k points)
+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}

 

Threfore answer= C
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
+4

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
+15 votes

Right answer is option C.

 

by Active (2k points)
0 votes

Let's see this one....

by (301 points)
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 Active (1.1k points)
Answer:

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
50,650 questions
56,194 answers
193,988 comments
94,864 users