GATE CSE 2017 | Set 2 | Question: 39

Question

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

• A. $\emptyset$
• B. $\{q_0, q_1, q_3\}$
• C. $\{q_0, q_1, q_2\}$
• D. $\{q_0, q_2, q_3 \}$

Comments

Very nice approach is mentioned in this link check it :https://youtu.be/kk7MLP0sPLo?si=PIwIXrftx-XetTnt  it will be helpful 😇

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

---

first make nfa using given table then check the tra.

Option C is correct

Answer 1

Answer is C.

 

Answer 2

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.

Answer 3

Extended transition function describes, what happens when we start in any state and follow any sequence of inputs.
If δ is our transition function, then the extended transition function is denoted by δ.
The extended transition function is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w).
The starting state is q2, from q2, transition with input “a” is dead so we have to use epsilon transition to go to other state.
With epsilon transition we reach to q0, at q0 we have a transition with input symbol “a” so we reach to state q1.
From q1, we can take transition with symbol “b” and reach state q3 but from q3, again we have no further transition with symbol “a” as input, so we have to take another transition from state q1, that is, the epsilon transition which goes to state q2.
From q2 we reach to state q0 and read input “b” and then read input “a” and reach state q1. So q1 is one of the state of extended transition function.
From q1 we can reach q2 by using epsilon transition and from q2 we can reach q0 with epsilon move so state q2 and q0 are also part of extended transition function.
So state q0,q1,q2.

Answer 4

I think C will be a very appropriate ans for this because as we can see by giving epsilon to q2 we can go to q0 and then we have to perform aba and then again epsilon

Answer 5

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

Answer 6

Just following the transitions with adding epsilon between them as this is a e-NFA