Recognizable Languages
Büchi automata recognize the ω-regular languages. Using the definition of ω-regular language and the above closure properties of Büchi automata, it can be easily shown that a Büchi automaton can be constructed such that it recognizes any given ω-regular language. For converse, see construction of a ω-regular language for a Büchi automaton.
- Deterministic versus non-deterministic Büchi automata
The class of deterministic Büchi automata does not suffice to encompass all omega-regular languages. In particular, there is no deterministic Büchi automaton that recognizes the language (0+1)*0ω (Any word that has an infinite suffix consisting of only 0's). We can demonstrate it by contradiction that no such deterministic Büchi automaton exists. Let us suppose A is a deterministic Büchi automaton that recognize (0+1)*0ω with final state set F. A accepts 0ω. So, A will visit some state in F after reading some finite prefix of 0ω, say after the i0th letter. A also accepts the ω-word 0i010ω. Therefore, for some i1, after the prefix 0i010i1 the automaton will visit some state in F. Continuing with this construction the ω-word 0i010i110i2... is generated which causes A to visit some state in F infinitely often and the word is not in (0+1)*0ω. Contradiction.
The class of languages recognizable by deterministic Büchi automata is characterized by the following lemma.
- Lemma: An ω-language is recognizable by a deterministic Büchi automaton iff it is the limit language of some regular language.
- Proof: Any deterministic Büchi automaton A can be viewed as a deterministic finite automaton A' and vice-versa, since both types of automaton are defined as 5-tuple of the same components, only the interpretation of acceptance condition is different. We will show that L(A) is the limit language of L(A'). An ω-word is accepted by A iff it will force A to visit final states infinitely often. Iff, infinitely many finite prefixes of this ω-word will be accepted by A'. Hence, L(A) is a limit language of L(A').
Read more about this topic: Büchi Automaton
Famous quotes containing the word languages:
“People in places many of us never heard of, whose names we can’t pronounce or even spell, are speaking up for themselves. They speak in languages we once classified as “exotic” but whose mastery is now essential for our diplomats and businessmen. But what they say is very much the same the world over. They want a decent standard of living. They want human dignity and a voice in their own futures. They want their children to grow up strong and healthy and free.”
—Hubert H. Humphrey (1911–1978)