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?
Asked By : Thang Do
Answered By : Raphael
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.
- For which there is a formal definition!
- Other acceptance criteria have been proposed, e.g. visit one final state infinitely often.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/56108
0 comments:
Post a Comment
Let us know your responses and feedback