3
$\begingroup$

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions?

It is extremely difficult for me to recognise the general struture of such automata and to formalize them in a synthetic way.

For example take this automata: Buchi automaton The $\omega$-regular expression I came up with was: $b^*a(a^\omega+(a^*b^+a)^\omega)$. The minimised solution someone else found, was this: $(b^*a)^\omega$.

PS: should I post this in the mathematics and/or theoretical computer science forum and/or computer science, too?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

A Büchi automaton is a finite automaton that one runs on infinitely long strings (length $\omega$), with the proviso that the string is accepted if infinitely often the machine had visited an accepting state.

In your example, which I picture here, it is clear that the accepted strings are exactly described by $(b^*a)^\omega$, because a string will be accepted just in case any $b$ occurring in it is eventually followed by an $a$.

enter image description here

In general, for a Büchi machine with just one accepting state, then the way I think about it is this. In order for a string to be accepted, it must first get from the start state to the accepting state for the first time, and then it must get from that accepting state back again to that accepting state again, infinitely many times. This simple idea tells you how to find the $\omega$-regular expression for the accepted strings. Namely, let $\tau$ be a regular expression for getting from the start state to that accepting state, and let $\sigma$ be a regular expression for getting from the accepting state back to the accepting state with a nonempty string. Putting them together, the accepted strings for the Büchi machine will be described by $\tau\sigma^\omega$. One follows $\tau$ to get to the accepting state, and then follows $\sigma$ infinitely many times in order to revisit it sufficiently.

If there is more than one accepting state, then a similar idea will work, simply by adding those expressions together, since for one of the accepting states (by pigeonhole), one must first get there and then revisit it $\omega$ many times.

Improve this answer
$\endgroup$
10
  • $\begingroup$ great explanation! $\endgroup$
    – Fabio
    Commented Apr 3, 2016 at 15:29
  • $\begingroup$ So I should try to formulate the acceptance condition in words (similarly to regular automata) $\endgroup$
    – Fabio
    Commented Apr 3, 2016 at 15:31
  • 1
    $\begingroup$ Sure it's possible, since you can just enumerate all smaller regexps (in number of symbols) and check for equivalence, but the problem is Pspace-hard, so there isn't any efficient algorithm to do so. $\endgroup$
    – logicute
    Commented Apr 3, 2016 at 19:47
  • 1
    $\begingroup$ You can always use the equivalence with the Büchi automata together with the closure by complementation and negation to check the equivalence of two $\omega$-regexps, since the emptiness problem is decidable for automata. $\endgroup$
    – logicute
    Commented Apr 3, 2016 at 20:45
  • 2
    $\begingroup$ yes, see here $\endgroup$
    – Fabio
    Commented Apr 11, 2016 at 15:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .