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?

Improve this question
$\endgroup$
5
  • $\begingroup$ It's "Büchi", the name of a person. $\endgroup$
    – Raphael ♦
    Apr 18, 2016 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, 2016 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, 2016 at 10:38
  • $\begingroup$ @Raphael Sadly the tag is missing an umlaut too. $\endgroup$
    – Hendrik Jan
    Apr 18, 2016 at 13:07
  • $\begingroup$ @HendrikJan Tags can not contain umlauts, for whatever reason. :/ $\endgroup$
    – Raphael ♦
    Apr 18, 2016 at 13:59

3 Answers 3

Reset to default
5
$\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.
Improve this answer
$\endgroup$
0
5
$\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.

Improve this answer
$\endgroup$
3
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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