{'fraction_non_alphanumeric': 0.04681463525490493, 'fraction_numerical': 0.006388404918819281, 'mean_word_length': 3.7911928381321074, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mathematical Approach in Automata and Automata Association

The transition structure of an automaton can be used to create a natural topology to the set of states of an automaton, generating, this way, a topological space. Probabilistic automata can also be modeled in terms of measure theory. A system of many automata would be reduced to simple mathematical structures and analyzed by a topological point of view.


Introduction
The Automata Theory advanced considerably after 50s, based in the formalization of languages and the way automata work, allowing a good understanding about the states and transition chains of a generic automaton. A second study line has been developed based in topological principles behind all the formal structure of an automaton. In opposition of the main lines, we could be not interested in analyze the behavior of an Automaton from its language, but in the set of states itself and relations between different set of states, it is, different automata.
We can get it clearer from a fresh notion about what is an automaton. One could think about automaton as a thing with states, some ability to receive and read messages, information, and change its states based in the known information. A machine in a production line, for example, can be described as an automaton, having different states which could be information about its position an currently actions or tasks, with some sensors sending electrical signs to tell the machine when to change its state and to which state go now.
The automaton notion also applies to computer softwares. States don't need to be physical actions or positions and the messages don't need to be sensors signs. There are actually even mechanical automata, with no electrical signs or similar thing.
The traditional study of an automata is focused in the set of possible messages it supports, its properties and how it defines the automaton as it is. But the present work has as object, the set of states, using mainly topological principles from mathematical theory. Also, we are interested in how different automata work together.
In the first part, we are going to introduce the mathematical tools used along the paper. This includes fast notes about topology, a bit of measure theory and probability, as well as a brief introduction to graph theory, not going further than we would need to understand the results. This part is not supposed to replace a course in the quoted areas, we just want to make a very short review or offer a easy and fast way to consult the topics without needing to reopen a big book.
In the second part, we start to applying the topological theory in automation theory, providing definitions about interesting automata properties and its relation with topological properties that the set of states can have. We will have a good amount of tools to analyze the structure of different automata.
In the third part we will briefly discuss the special cases of finite automata. We are going to spend some time looking for finite automata definitions and some of the already defined properties in this case, as well as using probability theory to create a more sophisticated and much more useful definition of Probabilistic Automaton, which we will be able to use in the fourth part.
In the forth and last part, our focus is in systems which involve multiple automata simultaneously. We want to build a way to identify how they can affect each other and provide tools to describe these interactions and the global result of them.

A Review of the Mathematical Theory involved
This section is supposed to make some exposure, not in a depth way, about the mathematical topics this article uses. Most of this part is intended to present topics in Topology, but there will fundamental points in Probability Theory and, hence, Measure Theory.

Topology
Topology studies intrinsic properties of sets. We won't care about how the set is immersed in some other space, but specifically about properties which are invariant under referential changes of view. Definition 1.1. Let X be a set and T a family of subsets of X, such that 1. ∅, X ∈ T ; 2. The union of an arbitrary number of members in T is also in T ; 3. The intersection of an arbitrary number of members in T is also in T .
The pair (X, T ) is called Topological Space.
The members of T are called open sets. Example 1.11. If R has the usual topology, which we didn't define but intuitively is how we work naturally in euclidean space, the unique connected subsets are the open intervals (a, b) for a, b ∈ R.
Definition 1.13. Let X be a set. A Closure operator in X is a function C : P(X) → P(X) which satisfies, for all S 1 , S 2 ⊂ X, ; C(C(S 1 )) = C(S 1 ).
A closure operator induces a topology in the set which it is defined. The resultant sets of the application of a closure operator are closed sets, its complementaries are open sets and define a topology.
For a further reading with more details and complements, the reader can search for many books and materials in Topology branch, for example, [4]. The material provides a better explanation which can be useful for a deeper understanding of the work.

Measure and Probability Theory
The measure theory looks for ways to associate values to subsets of a set, following some definitions. It can be used to define volume, for example. On the other hand, Probability Theory uses the measure theory ideas to associate probabilistic values to events.
. Given a set X, the set of parts of X is a σ-algebra which receives a special name of discrete σ-algebra. Example 1.16. A special σ-algebra is the Borel σ-algebra, usually called just Borel algebra. Defined as σ-algebras that can be build by union, intersections and complements between the open sets of a topology. Definition 1.17. An Exterior Measure in a set X is a function µ : P (X) → R + such that A intuitively known measure is the Lebesgue Measure. It corresponds to the basic notion of volume in R n .
such that x ∈ R. Definition 1.20. A Probability Space is a triple P = (Ω, A , µ), such that Ω is a set, A is a σ-algebra in Ω and µ is an exterior measure in A , in a way that µ(Ω) = 1.
We call Ω the Sample Space; A is the event set ; µ is a probability function and µ(A) | A ∈ A is the probability of the happening of the event A.
The probability of each value in this set be the value of the roll can be given by a function µ. The probability of an odd number be the result is given by µ({1, 3, 5}). If we have a FAIR dice, it means the results are equiprobable, we have µ({1, 3, 5}) = 1/2. In this case, an interesting σ-algebra would be the discrete σ-algebra.

useful Graph Theory Results
The graph theory came up with Euler and the Königsberg's bridge problem. We can think of graphs like a set of points connected by line segments. Each point represents an object which we call vertex. Each line represents a relation between vertices and we call the lines edges. Interesting examples of graphs can be cities connected by roads, users in a social web that are connected by a friendly relationship in the program. The edges can be directed, it would mean an edge is an unilateral relation. A graph with directed edges is a directed graph. We can be interested, for example, in find the number of edges a complete graph with n vertex. That is what we are going to do. Proof. We can go through a combinatory approach. We know every edge connect exactly two vertices. This way, we can simple use a combination to calculate the number of possible edges for a given number of vertices n.

Automata in Topological Spaces
Definition 2.1 (Automaton). An automaton is a triple A = (Q, Γ, δ), such that Q is the set of states of the automaton; Γ is a set called the input alphabet or input set of the automaton and Γ * is the set of strings of Γ, built by the Kleene star over Γ; δ : Q × Γ * → Q is called the transition function, satisfying δ(q, e) = q for all q ∈ Q and a given e ∈ Γ * named empty string and δ(q, ab) = δ(δ(q, a), b) for all a, b ∈ Γ * .
Γ is not necessarily a set of words as the ones used in human language, is a convention to use this term to refer to anything that can be "read" or understood by an automaton, being it sensor signs, mechanical stimuli, or even human words. This way we can hand concepts like "letter", "alphabet" and "word" in a broad sense.
As pointed in [6], there is at least one topology that for Q that makes it a topological space. Hence, we can associate to the set of states of the automaton, topological properties. Since Q is directly related with the automaton it defines, it is possible to associate topological properties to the automaton itself, reflecting the features of its set of states. As showed in [2] and reinforced in [6], σ is a closure operator in Q and, then, defines a topology for Q, which we call source topology, T σ . The first thing we can notice is the source topology is related with the transition structure of the automaton, so we can predict the existence of relations between properties in automata theory and topological properties of Q.
Some of the theorems presented in this article were proved in [3], [1], [6] and [5]. In addition, in these papers we can find other interesting results. We present some of them here in order to make easier to the reader access them, so it will not be necessary to search for another paper to see the basics properties and theorems in the area.

Definition 2.3. Given an automaton
A is said connected if it's not possible to define a separated subautomaton in A.
Definition 2.5. An automaton is retrievable if, and only if, for all p, q ∈ Q, and any m ∈ Γ * such that δ(q, m) = p, there is some x ∈ Γ * in a way that δ(p, x) = q.
We can say, intuitively, that any transition can be undone, existing, then, some string that can produce this result. We must pay attention in the fact that it doesn't has to exist only one string that can undone some transition or all transitions but, in general, for every transition, there is a string that undone it, these strings can be different for every transition.
Definition 2.6. An automaton is called reversible if, and only if, for all p, q ∈ Q and some m such that δ(q, m) = p, there is some x ∈ Γ in a way that δ(p, x) = q.
Notice the difference between retrievability and reversibility. While retrievable automata needs a string to undone some transition, a reversible automata only needs a letter. We can see every reversible automaton is also retrievable.
Theorem 2.7. If, and only if, an automaton is connected, then it is also retrievable.

Proof. (Retrievable) ⇒ (Connected):
If an automaton A = (Q, Γ, δ) is not connected, so we can find a separeted subautomaton So there is no transition from the set Q s to the set Q ′ , but it must exist some transition from the set Q ′ to the set Q s , otherwise, one of the sets would not be part of the automaton, because it could not be reached.
So must exist at least one irreversible transition, it means there is no way to undone this transition, characterizing a non retrievable automaton. We have showed that if an automaton is not connected, then it is not retrievable, taking the negative of the consequence we conclude that if an automaton is retrievable, then it is connected.
(Connected) ⇒ (Retrievable): If an automaton is not retrievable, then must exist some transition which can not be undone, what allows us to find a separated subautomaton. It is enough if the subautomaton have one of the states of the transition and doesn't have the other. Specifically, if the irreversible transition is δ(q ′ , m) = q, a subautomaton with the set of states equal the source of {q ′ } will be separated.
In this case, we have showed that if an automaton is not retrievable, then it is not connected. So we conclude that if the automaton is connected, then it is retrievable.
Definition 2.8. An automaton is called weakly connected if, and only if, for all p, q ∈ Q, there is at least one m ∈ Γ * such that δ(q, m) = p. Definition 2.9. An automaton is said to be strongly connected if, and only if, for all p, q ∈ Q, there is at least one x ∈ Γ such that δ(q, x) = p. Theorem 2.10. If an automaton is weakly connected, then it is also retrievable.
Proof. Let A = (Q, Γ, δ) be a weakly connected automaton. Suppose any pair of states p, q and the transition δ(p, m) = q, for some m ∈ Γ * . If the automaton is not retrievable, then can't exist some string m −1 such that δ(q, m −1 ) = p, which is an absurd, because if there wasn't a string that allows a transition from p to q, the automaton wouldn't be weakly connected.
Theorem 2.11. If an automaton is strongly connected, then it is also reversible.
Proof. The proof is analogous to the last theorem. Just changing the strings for letters would be enough.
Definition 2.12. Let A = (Q, Γ, δ) be an automaton. Select p, q ∈ Q and m ∈ Γ * . We call q a m-successor of p and we say p is a m-predecessor of q if, and only if, δ(p, m) = q.
We can see the source topology is closely related with the notion of successor and predecessor.
Organizing the properties here presented and considering the relations between them and its implications, we graph this diagram: The properties are presented as the Table 1. Arrows represents implications. For example, the property 1 (Strongly connected) implies property 2 (Reversibility), which also implies 4 (Retrievability). 4 and 5 implies each other.
Theorem 2.14. The following properties are inherited from automata by its subautomata: i Strongly connectivity ii Reversibility iii Connectivity Proof.
i Suppose q 1 and q 2 belonging to the set of states of an strongly connected automaton. By definition, there is a transition between these two states. If we select a subautomaton and it has q 1 and q 2 , we have the transition maintained due to the transition function being the same but with a reduced domain and range, which includes the two states.
ii Analogously, if two states of the automaton are in the subautomaton, the reversibility feature is inherited by the same property of the transition function. Both the transition and its inverse are maintained.
iii Analyzing the automaton A = (Q, Γ, δ) and a subautomaton A ′ = (Q ′ , Γ, δ ′ ) of A, since Q ′ ⊂ Q, there will not be subset of Q ′ which is not a subset of Q, it means, any subautomaton of A ′ is also a subautomaton of A. If A is connected, A ′ must be connected too, since the existence of a separated subautomaton in A ′ would imply the existence of a separated in A, which can not be the case since it is connected.
Theorem 2.15. Let A = (Q, Γ, δ) be an automaton. If, and only if, the source topology T σ is indiscrete, then A is connected.
Proof. (connected) ⇒ (Indiscrete Topology) If A is connected, it means the source of any subset of Q is Q it self, because all the states allow transition to every other state. It is, for every subset B ⊂ Q, σ(B) = Q by definition of connected automaton. This way, the unique open sets will be ∅ = σ(Q) C and Q = σ(∅) C since σ(∅) = ∅.
(Indiscrete Topology ) ⇒ (Weakly Connected) If the topology is indiscrete, the source of every subset of Q must be Q or ∅. Since Q ′ ⊆ σ(Q ′ ) ∀ Q ′ ∈ Q, a non-empty subset of Q will have source Q, which is not possible if there were a separated subautomaton.
If A ′ is separated, there won't be any state q ∈ Q, q ∈ Q ′ such that δ(q, m) = q ′ for some m ∈ Γ * and some q ′ ∈ Q ′ . This way, it is impossible that σ(Q ′ ) has more elements than Q ′ . But since C ⊆ σ(C) for any subset C, we conclude that We consider now the case in which A ′ is not separated. If A ′ is not separated, there exist q ∈ Q, q ∈ Q ′ such that δ(q, m) = q ′ for some m ∈ Γ * and some q ′ ∈ Q ′ . It means there is predecessor for at least one q ′ ∈ Q ′ . Then, by definition of source operator, σ(Q ′ ) = (Q ′ ). Since A ′ being not separated implies σ(Q ′ ) = Q ′ . The converse shows us that if σ(Q ′ ) = Q, then A ′ is separated. BAVEL shows us that an automaton is retrievable only if σ(Q ′ ) = Q ′ , ∀ Q ′ ∈ Q, which contradicts other two theorems that Bavel himself proves. He argues that an automaton is retrievable only if it is a disjoint union of weakly connected automata and in a weakly connected automaton holds that σ(Q ′ ) = Q ∀ Q ′ ⊂ Q. Of course it needs to exist some transition between the disjoint automata, otherwise, it wouldn't make sense to say they are the same automaton. If there is one or more transitions from one subautomaton to another one (considering they are disjoint automata) and there isn't a way to undone it, the automaton is not retrievable. If there is a way to undone the transitions between disjoint weakly connected subautomata, it will be, then, a retrievable automaton, since the retrievability of the subautomata are guaranteed by theorem 2.10. But in this case, since the disjoint subautomata are weakly connected and there are transitions in "both hands" between them, any subset will have source equal the whole set of states of the automaton, which disagree with BAVEL's theorem. These results used in our arguing are also proved by BAVEL and we showed that they contradict the statement that σ(Q ′ ) = Q ′ holds for a retrievable automaton.
We must just be careful at the definitions used, since our concept of weakly connected automaton corresponds to strongly connected automaton in BAVEL's work.
The next theorem is a non-conflicting version of the statement discussed above. We want to reformulate the theorem and prove it.
If the automaton A is retrievable, then it is connected by theorem 2.7, so A can't have a separated subautomaton. By theorem 2.16, a separeted subautoma- If a subautomaton has σ(Q ′ ) = Q ′ , it can't be separeted since theorem 2.16. If σ(Q ′ ) = Q ′ ∀ Q ′ ⊂ Q, the automaton is connected, because there won't be separated subautomata. This implies, by theorem 2.7, that it is a retrievable automaton.
Theorem 2.18. There is no automaton with more than one state and source topology equal the discrete topology.
Proof. Suppose an automaton A = (Q, Γ, δ) with more than one state. In order to the source topology be discrete, the set Q − {q}, for an element q ∈ Q, must be an open set. Hence, it must exist some q ′ ∈ Q such that σ({q ′ }) = {q}. Since the source operator has the following property: R ⊆ σ(R) ∀ R ⊂ Q, the only possibility is that q ′ = q. In addition, our supposition doesn't allows the existence of some state that have transition to q, because it would make σ({q ′ }) = {q}, q needs to have a transition to some state, or it will be the only state of the automaton. We conclude there is a p such that δ(q, m) = p for some m ∈ Γ * . Again, since we want a discrete topology, Q − {p} must be a open set. In order to this happening, it must exist some r ∈ Q in a way that It left us with the last possibility of r = p. Even this way we would have a problem, because there is a transition from q to p, so q ∈ σ({p}). Then, we will never have an open set Q − {p} and, hence, the topology will never be discrete if the automaton have more than one state. Definition 2.19 (Equality Between Automata). Let A = (Q 1 , Γ 1 , δ 1 ) and B = (Q 2 , Γ 2 , δ 2 ) be two automata, we say A is equal B if, and only if, 3. f (Im(δ 1 )) = Im(δ 2 ) and f 1 (Im(δ 2 )) = Im(δ 1 ), it is, δ 1 ∼ δ 2 .
Equal automata share the same properties and are, essencially, the same automaton.
Definition 2.20 (Homeomorphism of Automata). Two automata are homeomorphic if there is a homeomorphism between its set of states.
Homeomorphic automata share all the topological invariant properties.
We want to create one more correlation between automata. One that allows us to identify when two automata have the same properties even if there isn't a clear similarity between them. So lets consider the transition function δ. Notice that it is actually a two variable function, but lets decompose it in many one-variable functions.
For each m ∈ Γ * there is an unique function δ m : Q → Q, such that δ m (q) = δ(q, m). This way we will have a set of functions with same cardinality as Γ * . Now we have a set of endomorphisms that does the same as the transition function.
We can, then, create a second definition of an automaton.
ii Since there is the relation connectivity ⇔ retrievability, an automaton which is connected is also retrievable. So any congruent automaton will be also retrievable since the proof above and then, will be connected.
iii The proof is analogous to the retrievability version, but we use γ, x ∈ Γ instead of x ∈ Γ * . iv A weakly connected automaton allows transition from any state with some string m ∈ Γ * . But given a transition δ m (q) = p, exists, by the homeomorphism, δ ′ m (q ′ ) = p ′ . Using the property of the homeomorphism based on the definition of congruence of automaton, any other transition from p to some t, using δ n (p) = t | n ∈ Γ * , can be built with f (δ m (δ n (t))) = δ ′ m (δ ′ n (t ′ )) = t ′ . Which is valid for any t, including t = q, it means, any transitions that can be undone by some transition, will have its equivalent in the congruent automaton, as well as its -reverse transition.
v The proof is analogous, but, we assume n, m ∈ Γ.

Finite Automata
The discussed concepts are applicable to any automaton. But most of the automata in practice are Finite Automata. Finite automata are the ones which have a finite set of states. Given the importance of this kind of automata, we are going to dedicate a whole section to talk about the modeling of finite automata.
We want to define the two main kinds of finite automata, the deterministic and the probabilistic. We are also going to give a special attention to the probabilistic ones.

Deterministic Finite Automata
From now, we will define and present a property of deterministic finite automata. Deterministic automata are very well known in academy Q is a finite set, the set of states of the automaton; Γ is the input alphabet; δ : Q × Γ * → Q is the transition function, which satisfies δ(q, e) = q for all q ∈ Q and some e ∈ Γ * , the empty string, with the addition of δ(q, ab) = δ(δ(q, a), b) for all a, b ∈ Γ * and all q ∈ Q; q 0 ∈ Q is the inicial set of the automaton; F ⊂ Q it is the set of final states and when the automaton is on some state q f ∈ F , it stops its work.
This kind of automaton is said to be deterministic exactly because of its last feature: for some transition given by a pair of string and state, there is an unique resultant state.
We could think about representing an automaton as a directed graph. This, in fact, is often used in state-machine analyzes. The states of an automaton are presented as vertices of the graph, while the transitions are the edges.
A complete graph, in this approach, would mean a strongly connected automaton. The difference is in the fact we need to think about a complete graph and consider the two ways possible for directing the transitions (edges). Proof. Using the result given presented in 1.24, we consider the transitions as edges and conclude that the automaton must have n(n−1) 2 edges. But we also need to care about the direction of the edges and there are two directions possible for each edge. So we can just multiply the number of edges by 2 and we are counting, then, both directions. We finish with n(n − 1) edges.
The number of transitions could also be more because there would be more than one transition from a state q to a state p using different strings. Then, the number we got is the minimum number of edges, or transitions.
It is possible to find an existence condition for a finite strongly connected automaton has unique predecessors. Writing the number of elements of the set of states as n(Q) and the number of letters in the alphabet as n(Γ), we can notice that n(Q)−1 ≤ n(Γ), so there won't be distinct states allowing transition to the same state using the same letter.
If the automaton has n(Q) states and it is strongly connected, then must be, for each state, n(Q) − 1 transitions. Supposing a generic state q, each transition can be represented by an arrow going from a state to q. It must exist at least n(Q) − 1 letters, otherwise we would need to repeat letters with different arrows (transitions) and then our automaton wouldn't have a unique predecessor.

Probabilistic Finite Automata
Intuitively, the difference between deterministic and probabilistic automata is that, while, for a deterministic automaton, the transition function of a given pair state-string can lead us to an unique new state, for a probabilistic automaton, it could give us more than just one new state.
In a algebraic approach, we are going the define probabilistic automata using probability spaces.
Q is a finite set of states; Γ is the input alphabet; δ : Q × Γ * → P (Q) is the transition function, in which P (Q) means the power set of Q; q 0 ∈ Q is the initial state of the automaton; F ∈ Q is the set of final states of the automaton. This is the standard definition of a probabilistic finite automaton (PFA). Some articles discuss the interpretation of a probabilistic automaton. We are going to assume that the transition is made by the verification of a random variable and using its value to decide the next state. Based in this idea, we can bring a new definition using probability spaces.

Definition 3.4 (Alternative). A Probabilistic Finite
Automaton is a 5tuple A F P = (P, Γ, δ p , q 0 , F ) in which P = {P m1,q1 , P m1,q2 , ..., P m1,qn , P m2,q1 , ...} is a class of probability spaces; P mi,qj = (Q, A , µ mi,qj ). µ mi,qj : Q → [0, 1] is a function that receives a state q as input and gives the probability of the transition from q j to q by a string m i .
Q is the set of states of the automaton and A is a σ-álgebra in Q. Γ is the input alphabet of the automaton; δ p : Q×Γ * → (Q×[0, 1]) n in which n is the number of elements of Q, in a way that δ p (q i , m j ) = {(q 1 , µ mj ,qi ({q 1 })), (q 2 , µ mj ,qi ({q 2 })), ..., (q n , µ mj ,qi ({q n }))}; q 0 ∈ Q is the inicial state of the automaton; F ⊂ Q is the set of final states of the automaton.
The first observations we can do is that the set of states now is a sample space, subsets of Q are events and for each pair string-state, there is a probability function. The transition function δ p just gives us pairs of a state and its respective transition probability. When dealing with a subset with more than one state, we are computing the probability that the transition lead to any state inside this subset.
Another thing that can be noticed came from the definition of probability measure. Considering each state as a subset of Q, the union of all the states gives Q as result. By one of the conditions of the definition of exterior measure, we can see that µ mi,qj (∪ n l=1 {q l }) ≤ n p=1 µ mi,qj ({q p }). But since the union of all states is Q itself, we get µ mi,qj (Q) ≤ n p=1 µ mi,qj ({q p }). We also must remember that µ(Ω) = 1. The probability of an event can't be greater than 1, we conclude that the sum of the probabilities of all transitions is 1.
But notice we are not summing the probability related to subsets involving more than one state, like µ mi,qj ({q 1 , q 2 }), but only the isolated probabilities of the transition to each state.
With the classical definition of automaton, we saw that δ(q, nm) = δ(δ(q, n), m). An interesting question that could appear is how to extend this notion to our alternative definition of probabilistic automaton.
By the multiplicative principle, we just need to multiply the probability related to the first string with the probability related with the second string. We have δ p (q, m 1 m 2 ) = {(q l , n k=1 µ m1,qi ({q k })µ m2,q k ({q l })) | 1 ≤ l ≤ n} in which n is the number of states of the automaton. It gives us the probability of each state be reached from another given state and a chain of two strings. The summation is just the sum of the probabilities of all the possible transitions that starts in a state q and finishes in a state q l by making the whole transition in two steps, two smaller transitions (one for each string).
We can generalize this formula for a chain x of strings: Again, n is the number of states of the automaton.
Theorem 3.5. Given a chain of x strings, generated randomly in an alphabet of p strings, the chance of this chain leads successfully from a state q 1 to a state q f is x is the probability of the i-th chain of strings possible be chosen between all the possible chains, with m i j ∈ Γ * ∀ j. p x is the number of possible chains with x strings, resulting from a finite alphabet of p strings. In the case of infinity strings, one could just introduce the limit p x → ∞.
Proof. Calling P q1,A (q f ) the probability of the transition from the state q 1 to q f along the chain A. The probability of a given chain A with x strings in this alphabet be chosen in a random process between all the chains possible is P A . By the multiplicative principle, the probability of choosing this chain A and it successfully leads from q to q f is P A P q1,A (q f ).
If we sum this probability for all the possible chains, we will have the probability of a random chain makes the interested transition. This can be written as p x i=1 P Ai P q1,Ai (q f ), having A i as the i-th chain possible and p x as the number of chains possible. The term P q,Ai (q f ) is exactly the f-th element of the set δ p (q, A) and, then, we can replace the relation already showed to the probability of a given transition by a certain chain of strings, getting , which is the probability of, choosing a random chain of x strings and giving it as input to the automaton, it results in the transition from q 1 to q f . Notice that m i j is the j-th string of the i-th chain possible A i . We can even think about a equiprobable random process, in which every chain has the same chance to be chosen, 1 p x . We get . This last situation would only be possible in a automaton with a finite input alphabet, since the probability of each chain would go to zero if the number of strings increases to infinity.
A last note in probabilistic automata is that every deterministic automaton is also probabilistic. It is true since we can build a Deterministic Finite Automaton (DFA) using all the ideas from a PFA. Indeed, let p, q be two states of a DFA such that δ(q, m) = p, for some m ∈ Γ * . We could represent this transition in a PFA in which δ(q, m) gives us a probability 1 to the state p and a probability 0 for any other state different of p. This can be made for any transition of a DFA, so a DFA is just a PFA which transitions have probability 1 or 0.

Automata Association
Eventually, automata are used in groups. Two or more automata works simultaneously. Many times we can be interested in the combined results of the automata, analyzing a "global" situation instead of looking for each single automaton at a time.
The problem can became very complex when there are interactions between the automata, it is, the states and transitions of one interfere in the transitions or states of the other one. This kind of relation is very common in many systems, like security systems, where some actions are not allowed if some condition is not satisfied.
Lets model what we will call Dependence Forms Between Automata. Our goal is to formalize dependencies and relations between automata that works together. We want to build patterns for a "final automaton" which is equivalent to the system with many automata working in a group.
We are going to be able to build a resultant automaton, an unique automaton that contains all the features about the automata in the system and its different relations.

Independent Automata
We are going to call Independent automata, two or more automata that can be described by an unique automaton and the transitions, states and alpha-bet of one of the automata don't interfere in some other automaton. It means we can describe them in parallel.
Definition 4.1. The Resultant Automaton of a system of many automata is a single automaton that describes the whole system.
We can write the resultant automaton in a reduced form by R = (Q R , Γ R , δ R ). Notice the transition function can be represented by δ R : two probabilistic automata. We call A and B independent automata if, and only if, the resultant automaton is given by A ⊗ B = (P AB , Γ A × Γ B , δ, q 0 , F ).
The probability spaces are P mi,qj = ( l . Which is consequence of the multiplicative principle. This definition is more general since every deterministic automaton is also probabilistic. Proof. The product topology is defined for Q A ×Q B and it is a natural topology for its space. But there is also the source topology of the resultant automaton. What we need to show is that the two topologies are actually the same.
Suppose two open sets of the source topology U A ∈ T A and U B ∈ T B . U A × U B is an open set of the product topology T AB . V A and V B , such that But by the definition of the source operator, we see that which is an open set of the product topology. Since it is true for every subsets U A and U B , the product topology coincides with the source topology of the resultant automaton.
When two automata are finite and independent, the number of states of the resultant automaton is simply the multiplication between the number of states of the two automata.

Q-dependent automata
We are going to call Q-dependent automata the ones which are related in a way that the set of states of one interfere in the set of states of another. Specifically, we mean that given two automata A 1 and A 2 , there are states in A 1 that will be accessible only if the the current state of A 2 is in some specific subset and this relation can be a two-hand relation.
In a generic way, looking into two automata with set of states Q 1 and Q 2 , we can represent the situation in the following way: is the restricted set of Q 1 and V 2 ⊂ Q 2 is the condition set of U 1 . U 2 ⊂ Q 2 is the restricted set of Q 2 and V 1 ⊂ Q 1 is the condition set of U 2 . Notice the condition sets and restricted sets can have empty intersections or not. In addition, there can be more than one pair of restricted and conditions sets.
The logic is that for a given state q 0 ∈ Q 1 | q 0 ∈ U 1 , a transition from q 0 for some q ∈ U 1 is only possible if the current state of Q 2 belongs to V 2 . Also, the state q can continue in access only if the state of Q 2 still belonging to V 2 .
The set of states of the resultant automaton would be Q 1 × Q 2 if Q 1 and Q 2 were independents, but it is not the case now. We are going to work analyzing the set of states of the resultant automaton Q, which elements are pairs (q 1 , q 2 ), such that q 1 ∈ Q 1 and q 2 ∈ Q 2 .
The pairs in the form (q u1 , q 2 ) | q u1 ∈ U 1 , q 2 ∈ V 2 and (q 1 , q u2 ) | q u2 ∈ U 2 , q 1 ∈ V 1 can't occur, since the build of the relation between the sets. In this simpler case, we can write the set of states of the resultant automaton as In which U 1 is restricted by V 2 and U 2 is restricted by V 1 .
Theorem 4.6. Given two finite Q-dependent automata A and B, with set of states Q A and Q B , respectively, restricted and condition sets named as in 4.5.
The number of states of A⊗B is given by where η(K) means number of elements of the set K.
Proof. The proof is a direct consequence of the multiplicative principle and the operations between the sets that define Q. One could verify it by using operations with sets in the definition of Q.

Γ-dependent automata
Intuitively, Γ-dependent automata can be seen as automata in which certain transitions in one of the automata can only be done if the transition happening in the other automaton is using some specific strings. We say that A is Γ-dependent of B if, and only if, the resultant automaton is given by R = (Q, Γ, δ), where Q = Q A × Q B ; Γ = Γ A × Γ B and δ(q, m) = (δ A (q A , m A ), δ B (q B , m B )) with q = (q A , q B ) and m = (m A , m B ), along with the condition that for every pair (q i , m j ) | q i ∈ Q A , m j ∈ Γ * A , there is a set Γ qi,mj ⊆ Γ B such that the transition δ(q, m) = (δ A (q i , m j ), δ B (q B , m B )) is only defined if m B ∈ Γ qi,mj .
Initially is very attractive the idea that a Γ-dependence association has no impact in the set of states of the resultant automaton, but this idea is not correct, as we can see with the following example.
We can think about two simple automata that can be analyzed by hand. Consider the automaton A = (Q A , Γ A , δ A ), with Q A = {q 1 , q 2 }, Γ * A = {a, e} in which e is the empty string and the only defined transition using a is δ A (q 1 , a) = q 2 . Lets look also to the automaton B = (Q B , Γ B , δ B ), such that Q B = (q ′ 1 , q ′ 2 , q ′ 3 ), Γ * B = (b, γ, e) and the following transitions are defined (despite the ones that involves e): δ B (q 1 , b) = q 2 and δ B (q 1 , γ) = q 3 .
Suppose A is Γ-dependent of B and the transition δ A (q 1 , a) is defined only if the transition happening in B is by γ. We can see the set of states Q of the resultant automaton won't be simply Q A × Q B , since it is impossible to get the pair (q 2 , q ′ 2 ). By a counter-example we showed that a Γ-dependence relation can change the final resultant automaton.
So, to describe the set of states of the resultant automaton, we are going to think in the general case of two automata A = (Q A , Γ A , δ A ) and B = (Q B , Γ B , δ B ).
The transition in δ A (q i , m j ), being q i the i-th element of Q A and m j the j-th element of Γ * A , is associated with the set Γ B,i,j ⊆ Γ * B . Analogously, the transition δ B (q ′ i , m ′ j ), where q ′ i is the i-th element of Q B and m ′ j is the j-th element of Γ * B , is associated with the set Γ A,i,j ⊆ Γ * A . Calling Q R the set of states of the resultant automaton, the conditions to some state q = (q A , q B ) belong to Q R are: • For a q i | δ A (q i , m j ) = q A , ∃ γ p ∈ Γ B,i,j | δ B (q k , γ p ) = q B for some q k ∈ Q B ; • m j ∈ Γ B,k,p .
We also must apply the criteria to elements in Q B . This way we describe the set Q R . So a transition δ(q, m), with q = (q i , q p ) and m = (m j , m q ), is defined if m q ∈ Γ B,i,j and m p ∈ Γ A,p,q .

Conclusion
A study focused in the topological structure of the set of states of an automaton, based in its transitions generates an interesting amount of tools to analyze a state-machine or a system of state-machines.
We can realize that the development of the ideas related to the topology of an automaton can make easier the understanding or the description of statemachines in general. In addition, we presented concepts and theorems useful in the study and comparison of automata that have similarities, even if they look very distinct.
It was also possible to build a model of probabilistic automaton which makes viable the exploration of the transitions itself, by the computation of the involved probabilities.
We made possible to utilize ideas of set theory in order to build models of restrictions between automata, defining different relations and associations between different automata and building a resultant automaton which contains features of all the involved automata. This also makes possible to study some topological behaviour of the resultant automata and the associated automata.
The topological approach to analyze an automaton may not be enough to deal with all the problems involving state-machines, but it can be a powerful tool to simplify problems and systems. It is a good approach in order to transform problems in equivalent situations where one could solve in some easier way, even allowing us to get a new problem and solve it using old methods.