Question

enter image description here

In my opinon the Language recognised is this:

$(a + b)^* (ab)^ω$ but the solution provided is: $(a + b)^* (a + b)^ω$

Did I missunderstand the acceptance condition or is the solution wrong?

My reasoning is:
As far as I understood a Muller Automaton does accept a run if all the set of all infinitely often visited states can be found as acceptance condition.
E.g. if a run visits inf. often the states p & r and finitely often q then the set { p , r } has to be one of the set's of the acceptance condition.

I think in this case, that a word has to bounce inf. often between 2 of the 3 states (but is not allowed to visit the 3rd state inf. often). That means that in the end the word has to alternate between a & b inf. often after doing finitely often whatever it want's to do
=> $(a + b)^*$ ( = "do what ever you want to do finitly often and in the end") $(ab)^ω$ (= "iterate between a and b")

The given solution differs from my solution by accepting e.g. the following word: $aba^ω$

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top