Конечные автоматы и полугруппы

Форум для обсуждения вопросов математики

Модератор: Admin

teron
Сообщения: 3
Зарегистрирован: Сб янв 28, 2006 5:09 pm

Конечные автоматы и полугруппы

Сообщение teron » Сб янв 28, 2006 5:19 pm

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

Есть задача: по таблице переходов конечного автомата вычислить его полугруппу. Размер таблицы - 5*5.

Не может ли кто-нибудь разъяснить мне бестолковому, что такое полугруппа конечного автомата? :) Определение, данное в книге, я не могу понять уже полдня. Написано там следующее:
f : E*A -> B - произвольный автомат (* - декартово произведение).
Полугруппа автомата f (f_S) определятся отношением конгруэнтности (R) на полугруппе E*A, причем для элементов g, d из E*A g R d (g конгруэтно d) тогда и только тогда, когда для всех a, b из (E*A)1 (что еще за 1 в верхнем индексе?) выполняется f(agb) = f(adb).
Главная проблема заключается в понимании записи f(agb) = f(adb). Я знаю, что есть конечный автомат и понимаю, что получается при применении f, например, к a (паре "символ-состояние" из E*A). Но как применить f к тройке таких пар?

Насколько я понимаю, для нахождения полугруппы автомата нужно найти то самое R, то есть отношение конгруэнтности. Любые комментарии приветствуются. Заранее благодарен

IVVA
Сообщения: 1036
Зарегистрирован: Вт апр 05, 2005 6:44 pm

Сообщение IVVA » Сб янв 28, 2006 8:40 pm

Простите за, быть может, не тактичный вопрос:а что такое полугруппа, вообще, Вы знаете?

teron
Сообщения: 3
Зарегистрирован: Сб янв 28, 2006 5:09 pm

Сообщение teron » Сб янв 28, 2006 10:37 pm

Что же в нем нетактичного? Да, я знаю, что такое полугруппа. Это упорядоченная пара, первым элементом которой является множество, вторым - бинарная ассоциативная операция. Что-то в моем вопросе Вас смутило?

YuK
Сообщения: 698
Зарегистрирован: Вт дек 09, 2003 7:42 pm

Сообщение YuK » Пн янв 30, 2006 12:44 pm

http://www.exponenta.ru/soft/Others/gap/gap.asp - попробуйте эти ссылки посмотреть, там должен быть какой то форум