RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2010 Number 1, Pages 69–73 (Mi ivm6553)

The mirror image of the language of 2-synchronizing words

I. V. Petrov

Chair of Algebra and Discrete Mathematics, Ural State University, Ekaterinburg, Russia

Abstract: A word $w$ over a finite alphabet $\Sigma$ is called $n$-synchronizing if for each deterministic finite automaton $\mathscr A=\langle Q,\Sigma,\delta\rangle$ such that $|Q|=n+1$ the equality $|\delta(Q,w)|=1$ holds provided that $|\delta(Q,u)|=1$ for some word $u\in\Sigma^*$ (depending on $\mathscr A$). In this paper we prove that the language of all 2-synchronizing words is closed under the mapping that associates each word $w=a_1a_2\cdots a_t\in\Sigma^*$ with its mirror image $\overleftarrow w=a_t\cdots a_2a_1$.

Keywords: synchronizing word, universal synchronizing word, synchronizable automaton, mirror image, formal language.

UDC: 519.713

Received: 03.02.2007


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:1, 55–58

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024