RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2010, номер 1, страницы 69–73 (Mi ivm6553)

Зеркальный образ языка 2-синхронизирующих слов

И. В. Петров

Кафедра алгебры и дискретной математики, Уральский государственный университет, г. Екатеринбург

Аннотация: Слово $w$ над конечным алфавитом $\Sigma$ называется $n$-синхронизирующим, если для любого детерминированного конечного автомата $\mathscr A=\langle Q,\Sigma,\delta\rangle$ с $n+1$ состояниями выполняется равенство $|\delta(Q,w)|=1$ при условии, что $|\delta(Q,u)|=1$ для некоторого слова $u\in\Sigma^*$, зависящего от $\mathscr A$. В работе показано, что язык всех 2-синхронизирующих слов замкнут относительно отображения, ставящего в соответствие каждому слову $w=a_1a_2\cdots a_t\in\Sigma^*$ его зеркальный образ $\overleftarrow w=a_t\cdots a_2a_1$.

Ключевые слова: синхронизирующее слово, универсальное синхронизирующее слово, синхронизируемый автомат, зеркальный образ, формальный язык.

УДК: 519.713

Поступила: 03.02.2007


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:1, 55–58

Реферативные базы данных:


© МИАН, 2024