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

Hint:

Reachability in general: (Also used in CFG simplification)
State 'p' is reachable from state 'q' if there exists some path from 'q' to 'p' following the automatons transitions.

Reachability after reading a string: $\boldsymbol{\hat{\delta}(q, w)}$
Set of states reachable from 'q' only after consuming the entire string $\boldsymbol{w}.$

• For DFA, $\boldsymbol{\hat{\delta}(q, w)}$ always returns exactly one state.
• For NFA it returns a set of states.
• For an $\epsilon$-NFA, remember to apply $\epsilon$-closure at every step while computing $\hat{\delta}$.

---

(Golden Rule) :- Har symbol (a ya b) padhne se pehle sirf starting mein ε-closure lo. 

                            Aur har symbol padhne ke baad bhi ε-closure lena hai.

q2
│
│ ε
▼
{q2,q0}
│
│ a
▼
{q1}
│
│ ε
▼
{q0,q1,q2}
│
│ b
▼
{q0,q3}
│
│ ε
▼
{q0,q2,q3}
│
│ a
▼
{q1}
│
│ ε
▼
{q0,q1,q2}

---

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

Answer 1

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.

Comments

So ,sir we have to consider only those states which are used as epsilon move with string aba?

@Arjun

---

What does extended transition function mean?

---

extended transition function gives the state the Automaton reaches after processing a string like aba.

Answer 2

Right answer is option C.

 

Comments

The epsilon closure of any state must contain that state so after reading the $a$ and $b$, the epsilon closure of $q_3$ must by $\{q_3\}$

Answer 3

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

now applying Q2,a we go to Q₀ 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₁,Q2

so C should be correct answer here

Comments

Nice explanation.

---

@ Aboveallplayer 

Applying (Q2 on  'a') wont go to the state Q0 as there is no transition from Q2 on a

---

"now applying Q2,a we go to Q0 but as  lamda transition is there so it will also go to Q2 "

The above line is as wrong as any object can get... please dont provide such below grade answers.. and god knows why u gote so many upvotes..

Peace!

Answer 4

C is the answer.

Comments

mam, in which context it is written, is important !

---

There is a walk between q2 to q3 like this:
$\epsilon a b b$

Am I right?

---

bhai maja aa gya!! dhanyabad.
glad to see such elegant,nice answer

Answer 5

so ans is C

Comments

For making above state transition function, this state transition diagram will help a lot.

---

$\delta (q_{2},aba) = \epsilon (\delta (\epsilon (q_{2}),aba))$

this formula works here ????

---

Yes

Answer 6

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.

---

 

Comments

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.

 

B and D would be eliminated