Buchi Automata

Theory of Computation


A Finite-sate Automaton (FA) consists of

  • A finite input alphabet $\Sigma$

  • A finite set of states Q

  • A transition relation $\Delta\subseteq Q\times \Sigma \times Q$

  • A start state $q_0\in Q$

  • A set of accepting states $F\subseteq Q$

Then

  1. If the input is finite, i.e. in $\Sigma^*$, we have a non-deterministic FA (with no $\epsilon$ transitions)

  2. If the input is infinite, i.e. in $\Sigma^\omega$, we have A Buchi Automaton

  3. If $\Delta$ is a partial function $Q\times \Sigma \rightarrow Q$, we have a Deterministic Automaton

Acceptance conditions

NFA or DFA accepts a finite word $w_1w_2...w_n\in \Sigma^*$ if there is a sequence of states $r_0,r_1,r_2,...,r_n$ satisfying the following conditions

  1. $r_0=q_0$

  2. $(r_i,w_{i+1},r_{i+1})\in \Delta$ for every $i,-\leqslant i\leqslant n-1$

  3. $r_n\in F$

Buchi Automaton accepts $w_1w_2...\in \Sigma^\omega$ if there is a sequence of states $r_0, r_1,r_2,...\in Q^\omega$ satisfying the following conditions

  1. $r_0=q_0$

  2. $(r_i,w_{i+1},r_{i+1})\in \Delta$ for every $i,i>0$

  3. There are infinitely many $r_i$’s in F

Regular Languages

Regular language - Some DFA/NFA recognises it

Theorem
A language is regular iff it could be described by a regular expression

A regular language/expression is built upon the basic ones, which are any $s\in \Sigma$, the regular symbol $\epsilon$ or the empty language $\varnothing$, using the following operations (where A and B are regular)

  1. $A\cup B$, which is the set-theoretic union

  2. $A\circ B$ (or simply AB) which is $\{ab| a\in A, b\in B\}$

  3. A*, which is $\{a_1...a_n|a_i\in A, n\geqslant 0\}$

$\omega$-regular languages

$\omega$ regular language

An $\omega$-regular language/expression is built upon regular languages, using the following expressions

  1. $A\cup B$, where both A and B are $\omega$-regular
  2. $AB$, where A is regular and B is $\omega$-regular
  3. $A^\omega$, which is $\{a_1...| a_i\in A\}$, i.e. an infinite sequence of words from A, where A is regular and doesn’t contain the empty word
Theorem

An $\omega$-language is $\omega$-regular iff some non-deterministic Buchi Automaton recognises it

Limits of Regular Languages

Limit of a regular language

Let A be a regular language. The limit of A limA is the language $\{a\in \Sigma^\omega| \text{a has infinitely many prefixes in A}\}$

Theorem

An $\omega$-language is a limit of a regular language iff some deterministic Buchi Automaton recognises it