6. Büchi automata

Mikołaj Bojańczyk

zajęcia / courses

An $\omega$ -word is a word where positions are indexed by natural numbers. We write $\Sigma^\omega$ for the set of $\omega$ -words over an alphabet $\Sigma$ . To recognise languages of $\omega$ -words, we use Büchi automata (we will later move a monoid style).

Büchi automata. A nondeterministic Büchi automaton has the same syntax as a nondeterministic automaton over finite words (say, without $\epsilon$ -transitions), i.e. it is a tuple

$(Q,\Sigma,I,F,\delta) \qquad \mbox{with } I,F \subseteq Q \quad \mbox{and } \delta \subseteq Q \times \Sigma \times Q$

where $Q$ consisting of states, the input alphabet, initial states, final states, and transitions. Such an automaton accepts an $\omega$ -word if it admits some run which begins in an intial state and visits final states infinitely often. Call a language $\omega$ -regular if it is recognised by some nondeterministic Büchi automaton.

Example. The obvious question is: what about deterministic Büchi automata? As it turns out, these are too weak. Indeed, consider the set of $\omega$ -words over alphabet $\set{a,b}$ where the letter $a$ appears finitely often, this set can be described by the expression $(a+b)^*b^\omega$ . Here is a picture of a nondeterministic Büchi automaton that recognises this language:

We claim that no deterministic Büchi automaton recognises this language. Suppose that there would be such an automaton. Run this automaton on the word $ab^\omega$ . Since this word contains finitely many $a$ ‘s, it should be accepted, and therefore an accepting state should be used after reading some finite prefix $ab^{n_1}$ . Consider now the word $ab^{n_1} a b^\omega$ . Again this word should be accepted, and therefore there should be some $n_2$ such that an accepting state is seen after reading $ab^{n_1} a b^{n_2}$ . Iterating this construction, we get an $\omega$ -word of the form

$ab^{n_1} ab^{n_2} ab^{n_3} \cdots$

such that the automaton visits an accepting state before every $a$ , and therefore accepts, despite the word having infinitely many $a$ ‘s. Note how we crucially used determinism – by assuming that changing a suffix of the word does not change the run on a prefix. $\Box$

The automaton monoid and linked pairs

Our goal is to prove that nondeterministic Büchi automata are closed under complementation, and then a form determinisation: namely nondeterministic Büchi automata are equivalent to Boolean combinations of deterministic Büchi automata. Before proving these results, we show how to associate to each nondeterministic Büchi automaton a monoid homomorphism.

The automaton homomorphism. Consider a nondeterministic Büchi automaton with states $Q$ . For a finite run $\rho$ (i.e. a finite sequence of transitions), define the profile of the run to be the triple in $Q \times \set{0,1} \times Q$ such that the first coordinate is the source state, the last coordinate is the target state, and the middle coordinate says whether or not the run contains an accepting state (1 means yes). For a finite input word $w \in \Sigma^*$ , define it profile

$h(w) \subseteq Q\times \set{0,1} \times Q$

to be the set of all profiles of finite runs over this word. It is not difficult to see that the profile function $h$ is compositional, and therefore its image, call it $M$ , can be equipped with a monoid structure so that

$h : \Sigma^* \to M$

becomes a monoid homomorphism. This monoid homomorphism is called the automaton homomorphism associated to the automaton.

Linked pairs and factorisations. Define a linked pair in the monoid $M$ to be a pair of elements $s,e \in M$ such that $se = s$ and $ee=e$ . This notion makes sense in any monoid, but the following notion of accepting linked pair is specific to the monoid defined above. Define a linked pair to be accepting if there are some states $p,q \in Q$ such that $p$ is initial and the elements $s,e$ , when seen as sets of triples, satisfy

$(p,1,q) \in s \qquad \mbox{and} \qquad (q,1,q)$

If a linked pair is not accepting, then it is called rejecting.

For $s,e \in M$ and $w \in \Sigma^\omega$ , define an $(s,e)$ -factorisation of $w$ to be a factorisation

$w = w_0 w_1 w_2 \cdots$

into nonempty words such that $h(w_0)=s$ and

$h(w_i w_{i+1} \cdots w_j) = e \qquad \mbox{ for every }1 \le i \le j$

Note that the existence of such a factorisation implies that $(s,e)$ is a linked pair.

Büchi Linked Pair Lemma. A word $w \in \Sigma^\omega$ is rejected if and only if it admits an $(s,e)$ -factorisation for some rejecting linked pair $(s,e)$ .

Proof. Suppose that $w$ is rejected. Apply the Ramsey theorem, yielding some $(s,e)$ -factorisation for some linked pair. Clearly this pair must be rejecting, since otherwise we could construct an accepting run for $w$ . For the converse implication, suppose that $w$ admits an $(s,e)$ -factorisation, say

$w = w_0 w_1 w_2 \cdots$

for some rejecting linked pair. Define $x_i$ to be the position at the beginning of the word $w_i$ , in particular $x_0$ is the first position. We claim that there cannot be any accepting run on $w$ . Toward a contradiction, suppose that $w$ does admit an accepting run, call it $\rho$ . If $\rho$ is accepting, then by the pigeonhole principle one can find some $0 < i < j$ such that accepting states are seen between $x_i$ and $x_j$ , and the same state, call it $q$ , is seen in positions $x_i$ and $x_j$ . This means that there is some initial state $p$ that the word $w_0 \cdots w_{j-1}$ admits a run of profile $(p,1,q)$ . In other words, we have

$(p,1,q) \in h(w_0 \cdots w_{j-1}) = s$

By the same kind of reasoning, we conclude that

$(q,1,q) \in h(w_i \cdots w_{j-1})=e$

and therefore the linked pair $(s,e)$ is accepting, contradicting our assumption. $\Box$

Complementation of Büchi automata

As an application of the automaton homomorphism, we prove that languages recognised by nondeterministic Büchi automata are closed under complementation. This is Büchi’s original proof of the result. We will also use the same ideas to prove determinisation, which is done here.

Theorem. For every nondeterministic Büchi automaton, the complement of its language is recognised by a nondeterministic Büchi automaton.

Proof. Consider a language $L \subseteq \Sigma^\omega$ recognised by a nondeterministic Büchi automaton, and let $h : \Sigma^* \to M$ be the automaton homomorphism corresponding to this automaton. By the Büchi Linked Pair Lemma, the complement of $L$ is equal to

$\bigcup_{(s,e)} h^{-1}(s) (h^{-1}(e))^\omega$

with the union ranging over rejecting linked pairs. The above language is easily seen to be recognised by a nondeterministic Büchi automaton. $\Box$

COMMENTS

Skyeshcb

August 3, 2023

Consequently, each person of AsiaMe must be cautious whereas using the platform. The profiles are mostly properly-detailed, and while browsing, you will get the primary impression of a lady and decide whether or not she meets your expectations or not. And if anyone wants so as to add extra facts about themselves, they'll do it while organising the web page. When you come across a suspicious page on AsiaMe, it's good to report it instantly. When you step into the AsiaMe webpage, you can entry the advice web page with membersâ€™ profiles. The primary time you see the web site, you will admit its concise and straightforward interface. This means that instantly after registration, you will see the profiles of those women that you just might like. It implies that there is no assure that these details are real. After that, you have to provide some primary details and add a profile picture. Later, when you enter the portal as a registered user, you can go to your profile settings and add more details about your private life. To sum it up, you should use AsiaMe to seek out an Asian woman to dwell your life with. Meeting her in your site is the most fantastic expertise of my life. Other factors in our review go to the help group and measures that the site makes use of to eliminate pretend profiles. Nonetheless, poor verification of new members has resulted within the always rising number of pretend accounts. It is best to never send money or private information to anybody to avoid pretend profiles and fraudsters. Often, profiles at the location are comprehensive and include in-depth info that helps members to get an general impression of one another. Furthermore, it obtains hundreds of members in many nations world wide and numerous constructive opinions. Itâ€™s not as massive as another networks, since there are just two different websites in it, however it has numerous fans all over the world. Besides, they've also upgraded their app, however sadly, itâ€™s appropriate only for Android. The male to female ratio is 8.5: 1.5; thus, ladies have extra prospects. There are quite a lot of Asian women types to choose from. You will discover Asian women presently residing in the USA. However the relationship site might be accessed via the Qpid Network app. The platform may be accessed through the desktop or cellular version. This makes AsiaMe extra buyer-friendly, as more people can use the useful resource of their native language. You will want some time to know methods to register, where to purchase credits, and what communication instrument to make use of. The web site content seems a bit confusing from the primary glance, so you will definitely want some help to know it correctly. If you're willing to make use of this service, it's worthwhile to get registered first. You can too select to get 100 of them for 399 dollars. Another choice is to buy 16 credits for 96 dollars. For those who determine to buy credits, you will also be able to do it by way of the Qpid Community app. For example, writing or studying a message will value you one credit score. For instance, if you're new to the entire on-line dating world, you may find out how to stay secure during your search to your soulmate. Therefore, all members of the neighborhood are inspired to stay cautious. Despite that, you need to buy credits to communicate with the rest of the neighborhood. But why would you want to make use of them on the AsiaMe dating website? The second approach is just not available on asiame each relationship site, thatâ€™s why it is AsiaMeâ€™s special little function. Whichever cost method you choose, you will complete a transaction in a quick and handy manner. Get the full use of free services, like winks or likes, as that's an effective way to point out that you are excited about a specific woman and at the identical time itâ€™s fully free. Moreover, it has some free features, like creating an account, browsing profiles, utilizing superior search filters, uploading a profile photograph, and many others. Members require credit score points to ship messages and work together with others. All the capabilities are understandable, and also you wonâ€™t want any help to register your profile and start chatting with women. You only need to enter your title, date of delivery, and gender preferences. 2. Full a brief type by indicating your identify and last title, gender, delivery date, e mail and creating your password. This small kind requires you to enter fundamental data, resembling identify, gender, beginning date, and point out the email and password to sign up on the website later.

zajęcia / courses

6. Büchi automata

Leave a Reply