Доказать, что если в таблице переходов только перестановки, то полугруппа автомата является группой

задан 25 Апр '15 14:33

Было бы полезно дать все определения (кроме общепринятых), или указать ссылку. Дело в том, что все вещи связанные с заданием автоматов таблицам и прочим -- это вещи технические, и они могут сильно варьироваться. Здесь нет какого-то одного "образцового" способа. Даже само понятие автомата может использоваться в разных смыслах.

(25 Апр '15 14:46) falcao

@Яська: я сейчас подумал, что в данном случае можно обойтись без дополнительной информации. Это можно объяснить в достаточно общих терминах. Сейчас напишу.

(25 Апр '15 15:08) falcao

@Яська, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(25 Апр '15 16:04) Виталина
10|600 символов нужно символов осталось
1

Удобно представлять себе конечный автомат (конечность здесь существенна для доказательства) как размеченный ориентированный граф. Пусть $%S$% -- множество вершин графа, и $%A$% -- конечный алфавит символов. Каждое ориентированное ребро (т.е. ребро со стрелкой) имеет метку из $%A$%. По условию, для каждого $%s\in S$% и для каждого $%a\in A$% имеется одно и только одно ребро с меткой $%a$%, выходящее из вершины $%s$%. Тем самым, задаётся некоторое отображение из $%S$% в себя, которое можно записать в форме $%s\mapsto s\cdot a$%. Все такие отображения по всем $%a\in A$% порождают полугруппу, которая является подполугруппой в множестве всех отображений из $%S$% в себя, где операцией служит композиция.

Предположим, что для каждого $%a\in A$% отображение $%s\mapsto s\cdot a$% является перестановкой множества $%S$%. Тогда оно имеет обратное, но этого пока не достаточно для доказательства, потому что обратный элемент здесь должен принадлежать полугруппе автомата. Если доказать последнее, то это и будет значить, что эта полугруппа является группой.

Для каждого $%a\in A$% рассмотрим те рёбра ориентированного графа, которые помечены символом $%A$%. Мы знаем, что из каждой вершины выходит ровно одно такое ориентированное ребро. Начиная с какой-либо вершины, будем идти по стрелкам с меткой $%a$%. Ввиду конечности множества вершин, мы рано или поздно придём в вершину, которую уже посещали. При этом ни в какую вершину мы не можем прийти по ребру с меткой $%a$% двумя разными способами. Это следует из того, что наше преобразование, связанное с $%a$%, является перестановкой. Таким образом, мы придём рано или поздно в ту вершину, с которой начинали, и получится цикл из рёбер с меткой $%a$%.

Если не все вершины из $%S$% вошли в построенный цикл, то берём любую из не вошедших, и с ней делаем то же самое, то есть идём последовательно по рёбрам с меткой $%a$%. Из тех же соображений, мы рано или поздно вернёмся в вершину, с которой начинали. И так далее, пока все рёбра не окажутся разбиты на циклы. Ввиду конечности множества, это в какой-то момент произойдёт.

Пусть $%N$% есть наименьшее общее кратное длин всех получившихся при этом циклов. Тогда, если через $%\alpha$% обозначить перестановку на $%S$%, соответствующую $%a$%, получается, что $%\alpha^N=\mathbb 1$%, где $%\mathbb 1$% есть тождественная перестановка. В частности, $%\alpha^{N-1}\alpha=\alpha\alpha^{N-1}=\mathbb 1$%, откуда следует, что $%\alpha^{N-1}$% есть перестановка, обратная $%\alpha$%, и при этом она принадлежит полугруппе автомата. Это доказывает, что данная полугруппа является группой.

ссылка

отвечен 25 Апр '15 15:28

Мне не понятно, почему :"При этом ни в какую вершину мы не можем прийти по ребру с меткой a двумя разными способами. Это следует из того, что наше преобразование, связанное с a, является перестановкой." Может я не правильно понимаю, что значит перестановка.

(25 Апр '15 19:29) Яська
1

@Яська: в данном случае под перестановкой понимается взаимно-однозначное отображение множества S на себя. В таких случаях часто ещё говорят о подстановке. Если взять перестановку символов в обычном смысле этого слова -- например, 314562, то это означает, что 1 переходит в 3, 2 переходит в 1, и так далее. Если у нас окажется, что в вершину 7 можно прийти как из 3, так и из 8 (для примера), то это будет значить, что символ 7 стоит и на 3-м месте, и на 8-м, то есть это не перестановка.

Обсуждаемое условие является необходимым и достаточным для того, чтобы полугруппа была группой.

(25 Апр '15 19:35) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×51

задан
25 Апр '15 14:33

показан
311 раз

обновлен
25 Апр '15 19:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru