Let δ denote the transition function and d denote

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let δ denote the transition function and d denote the extended transition function of the ∈-NFA whose transition table is given below:

Then d (q₂, aba) is

1. φ
2. {q₀, q₁, q₃}
3. {q₀, q₁, q₂}
4. {q₀, q₂, q₃}

Correct Option: C

Converting the table to a state diagram then we get.

then, δ̂= (q₂ aba) All states reachable from q₂ by aba.
If aba is broken as ∈ , a , ∈ , ∈ , b , a then from q₂ it can reach q₁ and from there by null transaction to reach state q₂ as well as q₀.
Consider, (q₂ , a) = (q₂ , ∈ a) = {q₁ , q₂ q₀}.
(q₂ , ab) = (q₁ , b) = {q₀ , q₃ , q₂}
(q₂ , b) = {q₀ , q₂}
(q₀ , b) = {q₀ , q₂}
(q₂ , aba) = (q₀ , a) = {q₁ , q₂ , q₀}
(q₁ , a) = {q₂ , q₀}
(q₂ , a) = {q₁ , q₂ , q₀}
(q₃ , a) = {q₃}
Then, δ̂= (q₂ aba) = {q₁ , q₂ , q₀}
= {q₀ , q₁ , q₂}
Hence option (c) is correct.