Let's say I have this language: $(a + bc)^∗((b + c)a^ω + (abb^∗)^ω)$

It seems pretty complicated, where should I begin with if I were to construct a Büchi automaton?

I've been doing it the following way with smaller language sets:

  • a $^*$ operator is usually a path coming from a node to the same node.
  • a $+$ draws 2 branches

how would $^ω$ be represented? there are other operators, which I have not seen yet, what are they and how would they also be represented?

Pardon me if this is a silly question, but I'd rather ask than not knowing the answer ever.

Any help is greatly appreciated. Thang


1 Answer 1


You can construct an NBA for an $\omega$-regular expression $r$ by induction on the generating sequence of $r$, using the constructive closure properties of NBAs.

You can see some examples here

  • $\begingroup$ can you be more specific? or give me an example, please? $\endgroup$
    – Thang Do
    Apr 18, 2016 at 12:52
  • 2
    $\begingroup$ The construction usually leads to huge automata, so I can't really draw them here. Try looking at examples of the conversion from regular expressions to NFAs, you'll get the idea. $\endgroup$
    – Shaull
    Apr 18, 2016 at 14:11
  • 2
    $\begingroup$ @csessh Look in your course materials; the construction should be in there. IIRC, it's very similar to Thompson's construction for finite automata. $\endgroup$
    – Raphael
    Apr 18, 2016 at 14:14
  • $\begingroup$ this topic was briefly gone over in my course material/lecture, that's why I couldn't get much out of it and have to look to Google. but thanks for the keywords suggestion, it's getting a bit clearer to me now. $\endgroup$
    – Thang Do
    Apr 20, 2016 at 2:19

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.