In Figure 2.9, find S* (q0, 1011) and S* (q1, 01). Show the full computation. See attached image.

A nondeterministic automaton is shown in Figure 2.9. It is nondeterministic not only because several edges with the same label originate from one vertex, but also because it has a .-transition. Some transitions, such as (q2,0), are unspecified in the graph. This is to be interpreted as a transition to the empty set, that is, (q2,0) 0. The automaton accepts strings 1010, and 101010, but not 110 and 10100. Note that for 10 there are two alternative walks, one leading to qo, the other to q2. Even though q2 is not a final state, the string is accepted because one walk leads to a final state. Figure 2.9 Q1 Again, the transition function can be extended so its second argument is a string. We require of the extended transition function that if then Q, is the set of all possible states the automaton may be in, having started in state qi and having read w. A recursive definition of analogous to (2.1) and (2.2), is possible, but not particularly enlightening. A more easily appreciated definition can be made through transition graphs