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^ω$

  • 1
    $\begingroup$ What is your reasoning? Why do you think your answer is correct? Can you pick a single word that is in your language but not in the solutions (or vice versa) and tell us why you think it should be accepted by the automaton or not? Please spell out your reasoning; the more you give us to work with, the more likely we can clear up any misunderstandings. Don't make us guess what you are thinking. $\endgroup$
    – D.W.
    Feb 16, 2017 at 22:13
  • $\begingroup$ Don't use images for math or text. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). $\endgroup$
    – D.W.
    Feb 16, 2017 at 22:14

1 Answer 1


The solution given is incorrect.

The first clue that this might be the case is that $(a+b)^*(a+b)^\omega$ is a strange way to write anything: any finite number of $a$s and/or $b$s, followed by infinitely many $a$s and/or $b$s is just infinitely many $a$s and/or $b$s, so the given language is just a strange way of writing $(a+b)^\omega$.

Muller automata accept if the set of states visited infinitely often is one of the specified sets. To see that the automaton doesn't accept $(a+b)^\omega$, consider the word $a^\omega$. This is a member of $(a+b)^\omega$ but it's not accepted by the automaton, since the run on that word visits every state infinitely often, and $\{p,q,r\}$ is not an accepting set.

If exactly two of the automaton's states are visited infinitely often, then there must be a point at which the third state is never visited again. From that point onwards, the automaton can only alternate between the remaining two states, so any accepted word must end $(ab)^\omega$. While the automaton is still visiting all three states, it can read in any word so, yes, the accepted language is $(a+b)(ab)^\omega$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.