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

- $\emptyset$
- $\{q_0, q_1, q_3\}$
- $\{q_0, q_1, q_2\}$
- $\{q_0, q_2, q_3 \}$

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

+32 votes

the transition is nothing but (((Q2,a),b),a)

now applying Q2,a we go to Q_{0} but as lamda transition is there so it will also go to Q2

so now {(Q_{0,}Q2),b} = Q_{0,}Q2

now{(Q_{0,},Q2),a}=Q_{0,}Q_{1},Q2

so C should be correct answer here

+2

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

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

Therefore, answer (c)

States after input a -> q0, q1, q2

States after input b -> q0, q2, q3

States after input a -> q0, q1, q2

Therefore, answer (c)

+26 votes

+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 *δ*ˆ(*q*2,*a**b**a*) .Can you please help me out in this.

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

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?

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$

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

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

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

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$

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

+15 votes

+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

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

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

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.

52,221 questions

59,854 answers

201,034 comments

118,096 users