{'fraction_non_alphanumeric': 0.06363782825841792, 'fraction_numerical': 0.004994361205091026, 'mean_word_length': 3.421652421652422, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finite automata for testing uniqueness of Eulerian trails

We investigate the condition under which the Eulerian trail of a digraph is unique, and design a finite automaton to examine it. The algorithm is effective, for if the condition is violated, it will be noticed immediately without the need to trace through the whole trail.


Introduction
The problem of finding an Eulerian trail in a traversable directed pseudograph is well solved, and a counting formula is given in [3,2]. But in some applications, like reconstructing a string from its composition of short substrings, as discussed in various contexts [5,2,4,1], uniqueness rather than the exact number is mostly cared about, so the tedious calculation seems unnecessary. Considering a trail as a symbolic sequence over the set of vertices, Kontorovich showed that the unique Eulerian trails form a regular language [4]. We present a different proof by characterizing its complement, which leads to an effective implementation of a deterministic finite automaton (DFA) that accepts it, and gain an insight into its structure from the aspect of minimal forbidden words.

Results
In the following, we will freely switch the concepts from the theories of graph and formal language, and when the latter viewpoint is emphasized, the set of vertices V is noted Σ.

The language
Pevzner [6] proved that any two Eulerian trails of a digraph G can be transformed into each other by a series of operations called rotations and transpo-sitions. Roughly speaking, rotations correspond to the choice of initial vertex if the trail is closed, and a transposition swaps the order of two paths between a pair of vertices in the trail. Not losing generality, we always suppose that the initial vertex is fixed. Thus an Eulerian trail is not unique only if it has a transposition T : uaxbzaybv → uaybzaxbv, where a, b ∈ Σ, and u, v, x, y, z ∈ Σ * . If a = b, it degenerates to the form On the other hand, only x = y does not assure that the transposition makes a trail different, e.g. let x = ba and u = v = y = z = ǫ, then the trail in (1) becomes t = ababab, which is invariant under the operation, and is actually unique. To eliminate this case, we further request that the two a's before x and y on the left hand side of (1) or (2) are followed by distinct vertices. Then we call the corresponding transposition to be proper.

Lemma 1. Every non-identical transposition is equivalent to a proper transposition.
Proof. For any transposition T (t) = t, we can write it in the form of (1) or (2). If both a's are followed by a ′ , then let u ′ = ua.
(a) If x = ǫ and y = ǫ, then we can write x = a ′ x ′ and y = a ′ y ′ , and let z ′ = za. Otherwise, a ′ = b.
(b) If x = ǫ, then we can write y = a ′ y ′ , and let x ′ = za.
(c) If y = ǫ, then we can write x = a ′ x ′ , and let y ′ = za.
(a) If x = ǫ and y = ǫ, then we can write x = a ′ x ′ and y = a ′ y ′ . Otherwise, a ′ = a.
(b) If x = ǫ, then we can write y = a ′ y ′ , and let x ′ = ǫ.
(c) If y = ǫ, then we can write x = a ′ x ′ , and let y ′ = ǫ.
Substitute T ′ for T and repeat the above process, we will eventually get an equivalent proper transposition.
We conclude that an Eulerian trail t is unique if and only if it does not have a proper transposition. Let L be the language composed of unique Eulerian trails and L ′ be the language composed of those with proper transpositions, then they are complementary to each other.
By the definition of proper transposition, all sequences in L ′ have a unified form where u, v, w, y ∈ V * , b appears in aw, and the vertices next to the two a's are distinct. It results in a right-linear grammar G that generates L ′ : A a → cB acc |aC aa , B acb → dB acb |dB acd |aC cb , where a, b, c, d run over Σ. Therefore, L ′ is a regular language, and L = L ′ is also regular.

The finite automaton
Technically we can construct a finite automaton that accepts L from G(L ′ ), but it is more convenient to design it directly, like the following.  p ← a 14: end procedure Now we prove that the DFA M = (Q, Σ, δ, q 0 , F ) accepts L.
Proof. First we show L(M ) ⊂ L by proving its contrapositive. If t / ∈ L, then it has the form of (3). The design of M assures that c becomes BLACK m after b is inputed and remains so, thus M does not accept t.
Then we prove L ⊂ L(M ) by induction on the length of the input sequence t.
Basis: For |t| = 0, t = ǫ ∈ L. Since q 0 ∈ F , t ∈ L(M ). Induction: For |t| > 0, if t = sa ∈ L, then s ∈ L, and by the inductive hypothesis s ∈ L(M ). We prove t ∈ L(M ) by contradiction. Assume to the contrary that t / ∈ L(M ), then there are two cases: 1. If c a = BLACK just after s is inputed, then s must have the form ubwby, where a appears in bw and the vertices following the two b's are distinct. Thus sa ∈ L ′ , which contradicts t ∈ L.
2. If c a = WHITE just after s is inputed, then s must have the form upwp, where a appears in pw and the vertex following the first p is not a. Again sa ∈ L ′ , which contradicts t ∈ L.
We conclude that L(M ) = L.

Minimal forbidden words
Since L is a factorial language, i.e. for any t ∈ L, all factors of t also belong to L, it can be determined by its minimal forbidden words (MFW) [7]. A string r is a minimal forbidden word of L if r / ∈ L while all the factors of r belong to L. We categorize MFW(L) into sequences in the following two forms, which compose a language L ′′ : 2.
x, y, z do not contain a, b, and each two of x, y, z do not contain common vertices.
Proof. By definition all words in L ′′ are minimal forbidden words. Then we prove that L ′′ is complete, i,e. L ′ ⊂ Σ * L ′′ Σ * . For any t ∈ L ′ , it must has a form of (3), then r = awayb / ∈ L satisfies the condition 1. If it violates the condition 2, e.g. x / ∈ L, then let t = x. Repeat the above process until the condition 2 holds. Then if y contains a vertex c which appears in aw, t must have a prefix away ′ c / ∈ L. Therefore, t has a word r in the form (4) or (5) where y does not contain a, b or common vertex with x, z. Since reversing every edge's direction in a graph does not changes the number of its Eulerian trails, L is reversal. So we can also request that x does not contain a, b or common vertex with z.