# What are the steps/tricks/tips to construct a Büchi automaton from a given language?

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

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

• can you be more specific? or give me an example, please? – Thang Do Apr 18 '16 at 12:52
• 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. – Shaull Apr 18 '16 at 14:11
• @csessh Look in your course materials; the construction should be in there. IIRC, it's very similar to Thompson's construction for finite automata. – Raphael Apr 18 '16 at 14:14
• 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. – Thang Do Apr 20 '16 at 2:19