5
$\begingroup$

as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented.

From an assignment I'm working on, this automaton can be depicted as both infinite automaton and Büchi automaton.

Can you give me an example for each of those automatons to understand the differences?

$\endgroup$
  • $\begingroup$ It's "Büchi", the name of a person. $\endgroup$ – Raphael Apr 18 '16 at 10:23
  • $\begingroup$ yeah I know, but I can't type that u on my keyboard, and couldn't be bothered to copy&paste it from elsewhere $\endgroup$ – Thang Do Apr 18 '16 at 10:32
  • $\begingroup$ Remember that moment when you get upset at somebody misspelling your name. (I find the US Internation keyboard layout to be very convenient for typing most "western" names.) $\endgroup$ – Raphael Apr 18 '16 at 10:38
  • $\begingroup$ @Raphael Sadly the tag is missing an umlaut too. $\endgroup$ – Hendrik Jan Apr 18 '16 at 13:07
  • $\begingroup$ @HendrikJan Tags can not contain umlauts, for whatever reason. :/ $\endgroup$ – Raphael Apr 18 '16 at 13:59
4
$\begingroup$

The automaton models themselves, that is the syntax, are indeed identical: both have a finite set of states, a transition relation, and initial and final state(s).

The difference lies in the acceptance criteria, that is the semantics.

A finite automaton $A$ accepts a word $w$ if and only if there is a computation¹ for $w$ in $A$ that ends in a final state.

A Büchi automaton $B$ accepts a word $w$ if and only if there is a computation¹ for $w$ in $B$ that visits final states infinitely often².

The differences follow from this.


  1. For which there is a formal definition!
  2. Other acceptance criteria have been proposed, e.g. visit one final state infinitely often.
$\endgroup$
3
$\begingroup$

There is no difference in the specification (syntax). The only difference is in the interpretation (semantics). The language accepted by a DFA consists of finite strings defined in a certain way given the DFA, and the language accepted by the corresponding Büchi automaton consists of infinite strings defined in a certain way.

Indeed, you can leverage this connection to prove results such as:

An $\omega$-language is recognizable by a deterministic Büchi automaton iff it is the limit language of some regular language.

For a proof, see Wikipedia.

$\endgroup$
2
$\begingroup$

There are two main differences. First, finite automata are used to recognize sets of finite words and Büchi automata are designed to recognize sets of infinite words. The second main difference is that finite deterministic and finite nondeterministic automata have the same expressive power: both accept the regular languages, but the situation is different for Büchi automata: as Yuval Filmus pointed out, deterministic Büchi automaton accept the limit of regular languages, but nondeterministic automata accept the whole class of $\omega$-regular languages and these two classes are distinct. However, there do exist classes of deterministic $\omega$-automata that recognize exactly the class of $\omega$-regular languages, for instance Muller automata, parity, Rabin, or Streett automata.

$\endgroup$
  • $\begingroup$ In the case given in my diagram, if it's a Büchi automata, would this be an accepted language? aω(b +c)(a*(b+c))ω ? $\endgroup$ – Thang Do May 28 '16 at 6:50

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.