|
Известия высших учебных заведений. Математика, 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$.
Ключевые слова:
синхронизирующее слово, универсальное синхронизирующее слово, синхронизируемый автомат, зеркальный образ, формальный язык.
Поступила: 03.02.2007
Образец цитирования:
И. В. Петров, “Зеркальный образ языка 2-синхронизирующих слов”, Изв. вузов. Матем., 2010, № 1, 69–73; Russian Math. (Iz. VUZ), 54:1 (2010), 55–58
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm6553 https://www.mathnet.ru/rus/ivm/y2010/i1/p69
|
Статистика просмотров: |
Страница аннотации: | 406 | PDF полного текста: | 37 | Список литературы: | 26 | Первая страница: | 3 |
|