Shuffle Decomposition of Regular Languages
Masami Itō · 2020
Abstract: Let A ⊆ X ∗ be a regular language. In the paper, we will provide an algorithm to decide whether there exist a nontriviallanguage B ∈I(n, X) and a nontrivial regular language C ⊆ X ∗ such that A = B ⋄ C Key Words: regular language, shuffle product, shuffle decomposition, I(n, X) Category: F.1 In this paper, we will deal with shuffle decompositions of regular languages over an alphabet X. Regarding definitions and notations concerning formal languages and automata, not defined in this paper, refer, for instance, to [1]. Now let A = (S, X, δ, s0,F) be a finite automaton with L(A) =A and let B =(T,X,γ,t0,G) be a finite automaton with L(B) =B. We will look for a regular language C over X such that A = B ⋄ C. ByX, we denote the language {a | a ∈ X} with X ∩ X = ∅. LetB =(T,X ∪ X ∪{#}, γ,t0,G)whereγ is defined as follows: For t ∈ T and a ∈ X, γ(t, a) =t, γ(t, a) =γ(t, a). Moreover, γ(t, #) = t if t ∈ G. Then the following can be easily shown. Fact 1 Let a1a2...an ∈ X ∗ where ai ∈ X, i =1, 2,...,n.Thena1a2...an ∈ L(B) if and only if u1a1u2a2...unanun+1 # ∈L(B) where u1,u2,...,un ∈ X ∗. Let A1 =(S,X∪X ∪{#}, δ, s0, {α, ω})andletA2 =(S,X∪X ∪{#}, δ, s0, {α}) where S =( ∪ a∈X∪{λ}S (a) ) ∪{α, ω}. HereS (λ) is regarded as S where λ is the empty word. For s ∈ S, t ∈ S \\F, t ′ ∈ F, a ∈ X ∪{λ},b ∈ X and {#}, δ is defined as follows: