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

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

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

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

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

$r_0=q_0$

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

$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

$r_0=q_0$

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

There are infinitely many $r_i$’s in F

**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)

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

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

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

$\omega$ regular language

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

- $A\cup B$, where both A and B are $\omega$-regular
- $AB$, where A is regular and B is $\omega$-regular
- $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

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