The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
100 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
asked in Theory of Computation by (477 points) | 100 views

1 Answer

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

answered by Active (1.4k points)
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}


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

38,106 questions
45,608 answers
132,245 comments
49,230 users