gotchaMinor
What is the difference between finite automata and Büchi automata?
Viewed 0 times
thefinitewhatautomatabüchidifferencebetweenand
Problem
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?
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?
Solution
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.
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.
- For which there is a formal definition!
- Other acceptance criteria have been proposed, e.g. visit one final state infinitely often.
Context
StackExchange Computer Science Q#56108, answer score: 5
Revisions (0)
No revisions yet.