202401041201
Tags : Automata Theory
Büchi Automata
A Büchi Automata is a modification of a Finite State Automaton, so that it can accept infinite words.
A Büchi Automata is a tuple where is a Transition System and is a set of good states.
A word is accepted by the automata if it has a run that goes over good states, infinitely many times.
determinism is weaker
Example Language where the alphabet is Proof: We construct a word in the following manner.
- We keep reading ‘s until we reach a good state, then we read an and ‘s again until we reach another good state. We keep doing that until one of the good states is repeated, and we pump that section giving a word with infinite number of ‘s that is accepted by the automata.
- We also can get to a new state because at any point, if we decide to stop and just accept ‘s we get an accepted word, so a sequence of ‘s must take us to a good state in finitely many steps.
This weakening makes sense because the powerset construction just holds the information about the states that can be reached. You necessarily lose power about the set of sub-runs and where those can reach. This is fine for a finite automata, because acceptance only depends on reachability. For a Büchi Automata, the path taken, i.e the run itself matters, hence the powerset construction does not carry enough information to keep the same automata.