Omega automata, Problem 5a. February 17, 2021

Question

May I know in the question below, how the NDetF automata formula and transition diagram are written for [a SU b] with only one state variable?

Answer 1

Maybe I do not understand you question, but with one state variable q, we have two states, namely one where q is false and another one where q is true. These states are represented as {} and {q}, respectively.

Comments

Yes. We have two states {} and q.
We are in the initial state {} and for [a SU b], if the input is a and !b we will be in {}.
Once we get input b(a SU b is satisfied), we move to the acceptance state.

Here, I am able to draw the transition diagram first based on a SU b
Then I am finding the transition relation for the automata.

Is this the only way to solve this question or
Is it possible to write the automata for a SU b first and then go for the transition diagram?

---

There are certainly many ways how you can proceed here, and there are also many possible automata which are correct.

---

Thanks for clarifying, Professor.