The mirror image of the language of 2-synchronizing words
I. V. Petrov · Russian Mathematics · 2010
Aword w over a finite alphabet Σ is said to be n-synchronizing if for each deterministic finite automaton = 〈Q, Σ, δ〉 such that |Q| = n + 1, the equality |δ(Q,w)| = 1 holds provided that |δ(Q, u)| = 1 for some word u ∈ Σ* (depending on ). We prove that the language of all 2-synchronizing words is closed under the map that sends every word w = a 1 a 2...a t ∈ Σ* to its mirror image $$ \overleftarrow w $$ = a t ...a 2 a 1.