122 views

Let δ denote the transition function and α denoted the extended transition function of the ε-NFA whose transition table is given below:

Which of the following option is correct?

A) α (q1,aba) is {q0, q2}

 B) null reachable states are {q0, q1, q2}B
C) α (q3,bab) is {q0, q1, q2, q3}
 D) None of these

+1 vote

Option C :  α (q3,bab) is {q0, q1, q2, q3}

Considering the below ε-NFA , state q3 on i/p 'b' makes a transition to state q2 and then from state q2 on epsilon transition we can reach to q0 & from there on i/p 'a' state q0 reaches to q1 & at last on i/p 'b' state q1 makes a transition to state q3.

Transition : bεab => bab  (since, ε.R = R.ε = R )

0

@Kajal mam why not (A) is answer
bcoz (A) is {q0,q1,q2} Right ?

and what about (C) why it is false ?

0
Let me remind you that question is asking about which one is correct option..isn't it??
0
then mam how can you so sure ?
sorry i don't want to sound rude :D
0
ohh sorry from my side too...

In NFA with epsilon transitions, extended transition function gives all states reachable from q after reading an input symbol including epsilon transitions.

C is the only correct option and the reason i have explained in the answer added as long as i know.

In option A, extended transition function is there for q1 and the input is aba then it can be clearly seen from the epsilon NFA shown above that with states q0 and q2 it is not possible to accept the string aba ..one more thing here we are starting with q1 itself and it is not taken which is wrong this makes A as false. It should be {q0,q1,q2}

+1 vote
1