Exam question Omega Automata 17.02.2021

Question

Exam Question 17.02.2021 Problem 5 (c) 2021.02.17.vrs.solutions.pdf (uni-kl.de)

Q. I have some doubt in this solution, to determinize the NDetF automata we can check if its total and if its total then apply subset construction otherwise we can try to make it total by adding sink state and check if its meaning is same otherwise convert it to FG and apply breakpoint construction. Is this right ?

Q. So here I think the examiner tries to solve it by adding a sink state "r" as its meaning is same as NDetF then it is fine. Is my understanding correct ?

I also tried to solve this by just adding a sink state but without the dangling state {q,r}

Also is it Ok if I do not include dangling state {q,r} ?

Q. Could you please suggest a concrete way to check whether two automata is same in respect to acceptance condition other than just doing it intuitively ?

Answer 1

First Question: Yes.

Second Question: To make the automaton of part (a) totally defined, you just need to add a sink state as you did. However, part (c) also asks for a symbolic encoding of that automaton, and for the three states that you have, you need two state variables which in turn introduces a fourth state that must also have outgoing transitions for all inputs. So, you cannot solve the entire part (c) without the fourth state.

Third Question: A precise algorithm to check equivalence of the automata is difficult. You would have to determinize them and then you would have to check the equivalence of their acceptance conditions on their product automaton. While that can be done, it is certainly not recommended for the exam problems. Here, you better argue intuitively by reasoning about the words accepted from the states.

Comments

I understand your point.
Thanks for the detailed explanation.