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


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

| cite | improve this answer | |
  • $\begingroup$ can you be more specific? or give me an example, please? $\endgroup$ – Thang Do Apr 18 '16 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 '16 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 '16 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 '16 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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