## NFA

Question 1 |

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

Then is

∅ | |

{q _{0},q_{1},q_{3}} | |

{q _{0},q_{1},q_{2}} | |

{q _{0},q_{2},q_{3}} |

Question 1 Explanation:

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 q

With epsilon transition we reach to q

From q

From q

From q

So state q

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 q

_{2}, from q_{2}, transition with input “a” is dead so we have to use epsilon transition to go to other state.With epsilon transition we reach to q

_{0}, at q_{0}we have a transition with input symbol “a” so we reach to state q_{1}.From q

_{1}, we can take transition with symbol “b” and reach state q_{2}but from q_{2}, again we have no further transition with symbol “a” as input, so we have to take another transition from state q_{1}, that is, the epsilon transition which goes to state q_{2}.From q

_{2}we reach to state q_{0}and read input “b” and then read input “a” and reach state q_{1}. So q_{1}is one of the state of extended transition function.From q

_{1}we can reach q_{2}by using epsilon transition and from q_{2}we can reach q_{0}with epsilon move so state q_{2}and q_{0}are also part of extended transition function.So state q

_{0},q_{1},q_{2}.
There is 1 question to complete.