Is there any systematic (algorithmic) method to convert a regular expression like


to an automaton (let's say a Buchi automaton)?

  • 1
    $\begingroup$ Regular expressions connote languages of finite words, whereas Büchi automata accept infinite words. On the other hand, regular expressions are classically equivalent in power to DFAs, and there is a very simple algorithm that converts a regular expression to an NFA. You can find it in any decent textbook. $\endgroup$ – Yuval Filmus Jan 17 '17 at 18:13

There are (at least) three algorithms that convert a regular expression to an equivalent finite-state automaton:

Büchi automata enter the picture if you are working with $\omega$-regular expressions. See e.g. this description of the algorithm for constructing an equivalent Büchi automaton from an $\omega$-regular expression.


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.