edited by
28,050 views
77 votes
77 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

  1. $\emptyset$
  2. $\{q_0, q_1, q_3\}$
  3. $\{q_0, q_1, q_2\}$
  4. $\{q_0, q_2, q_3 \}$
edited by

12 Answers

18 votes
18 votes

so ans is C

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


 

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

edited by
1 votes
1 votes
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:

Related questions