Полуавтомат

В математике и теоретической информатике полуавтомат имеющий — это детерминированный конечный автомат, входы, но не имеющий выхода. Он состоит из набора Q состояний , , набора Σ, называемого входным алфавитом, и функции T : Q × Σ → Q называемой функцией перехода.

С любым полуавтоматом связан моноид называемый характеристическим моноидом , входным моноидом , переходным моноидом или системой переходов полуавтомата, который действует на множестве состояний Q. , Это можно рассматривать либо как действие свободного моноида строк , либо как индуцированную полугруппу преобразований Q во входном алфавите Σ .

В старых книгах, таких как Клиффорд и Престон (1967), полугрупповые действия называются «операндами».

В теории категорий полуавтоматы по существу являются функторами .

Полугруппы преобразований и моноидные действия

Полугруппа преобразований или моноид преобразований — это пара $(M,Q)$ состоящее из множества Q «множеством состояний ») и полугруппы или моноида M функций Q , или «преобразований», отображающих (часто называемого в себя. Они являются функциями в том смысле, что каждый элемент m из M является отображением $m\colon Q\to Q$ . Если s и t - две функции полугруппы преобразований, их произведение полугруппы определяется как их функциональная композиция. $(st)(q)=(s\circ t)(q)=s(t(q))$ .

Некоторые авторы считают «полугруппу» и «моноид» синонимами. Здесь полугруппа не обязательно должна иметь единичный элемент ; моноид — это полугруппа с единичным элементом (также называемым «единицей»). Поскольку понятие функций, действующих на множество, всегда включает в себя понятие тождественной функции, которая при применении к множеству ничего не делает, полугруппу преобразований можно превратить в моноид, добавив тождественную функцию.

М -действия

Пусть M — моноид , а Q — непустое множество. Если существует мультипликативная операция

\mu \colon Q\times M\to Q

(q,m)\mapsto qm=\mu (q,m)

который удовлетворяет свойствам

q1=q

для 1 единица моноида, а

q(st)=(qs)t

для всех $q\in Q$ и $s,t\in M$ , то тройка $(Q,M,\mu )$ называется правильным М -действием или просто правильным действием . В длинной руке, $\mu$ — это правое умножение элементов Q на элементы M . Правильный поступок часто записывается как $Q_{M}$ .

Левый акт определяется аналогично:

\mu \colon M\times Q\to Q

(m,q)\mapsto mq=\mu (m,q)

и часто обозначается как $\,_{M}Q$ .

М - акт тесно связан с моноидом преобразований. Однако элементы M не обязательно должны быть функциями как таковыми , они просто элементы некоторого моноида. Поэтому необходимо требовать, чтобы действие $\mu$ быть согласованным с умножением в моноиде ( т.е. $\mu (q,st)=\mu (\mu (q,s),t)$ ), так как, вообще говоря, это может не выполняться для некоторых произвольных $\mu$ , так же, как и для композиции функций.

Как только это требование выдвинуто, можно совершенно безопасно опустить все круглые скобки, поскольку произведение моноида и действие моноида на множестве полностью ассоциативны . В частности, это позволяет представлять элементы моноида в виде строк букв в компьютерном смысле слова «строка». Эта абстракция затем позволяет говорить о строковых операциях в целом и в конечном итоге приводит к концепции формальных языков как состоящих из строк букв. ^{[ нужны дальнейшие объяснения ]}

Другое различие между M -актом и моноидом преобразования состоит в том, что для M -акта Q два различных элемента моноида могут определять одно и то же Q. преобразование Если мы потребуем, чтобы этого не происходило, то М -акт по существу есть то же самое, что и моноид преобразования.

M -гомоморфизм

Для двух М -актов $Q_{M}$ и $B_{M}$ разделяющий один и тот же моноид $M$ , M -гомоморфизм $f\colon Q_{M}\to B_{M}$ это карта $f\colon Q\to B$ такой, что

f(qm)=f(q)m

для всех $q\in Q_{M}$ и $m\in M$ . Множество всех M -гомоморфизмов обычно записывается как $\mathrm {Hom} (Q_{M},B_{M})$ или $\mathrm {Hom} _{M}(Q,B)$ .

M - акты и M -гомоморфизмы вместе образуют категорию, называемую M -Act . ^[1]

Полуавтоматический

Полуавтомат – это тройка $(Q,\Sigma ,T)$ где $\Sigma$ — непустое множество, называемое входным алфавитом , Q — непустое множество, называемое множеством состояний , а T — функция перехода

T\colon Q\times \Sigma \to Q.

Когда набор состояний Q является конечным множеством (это не обязательно), полуавтомат можно рассматривать как детерминированный конечный автомат. $(Q,\Sigma ,T,q_{0},A)$ , но без начального состояния $q_{0}$ или набор состояний принятия A . С другой стороны, это конечный автомат , у которого нет выхода, а есть только вход.

Любой полуавтомат индуцирует акт моноида следующим образом.

Позволять $\Sigma ^{*}$ быть свободным моноидом, порожденным алфавитом $\Sigma$ (так что под индексом * понимается звезда Клини ); это набор всех строк конечной длины , состоящих из букв в $\Sigma$ .

За каждое в слово $\Sigma ^{*}$ , позволять $T_{w}\colon Q\to Q$ — функция, определенная рекурсивно следующим образом для всех q в Q :

Если $w=\varepsilon$ , затем $T_{\varepsilon }(q)=q$ , так что пустое слово $\varepsilon$ не меняет состояние.
Если $w=\sigma$ это письмо в $\Sigma$ , затем $T_{\sigma }(q)=T(q,\sigma )$ .
Если $w=\sigma v$ для $\sigma \in \Sigma$ и $v\in \Sigma ^{*}$ , затем $T_{w}(q)=T_{v}(T_{\sigma }(q))$ .

Позволять $M(Q,\Sigma ,T)$ быть набором

M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.

Набор $M(Q,\Sigma ,T)$ закрывается при композиции функции ; то есть для всех $v,w\in \Sigma ^{*}$ , у одного есть $T_{w}\circ T_{v}=T_{vw}$ . Он также содержит $T_{\varepsilon }$ , которая является тождественной функцией на Q . Поскольку композиция функций ассоциативна , множество $M(Q,\Sigma ,T)$ является моноидом: его называют входным моноидом , характеристическим моноидом , характеристической полугруппой или переходным моноидом полуавтомата. $(Q,\Sigma ,T)$ .

Характеристики

Если множество состояний Q конечно, то функции перехода обычно представляются в виде таблиц переходов состояний . Структура всех возможных переходов, управляемых струнами в свободном моноиде, графически изображается в виде графа де Брейна .

Множество состояний Q не обязательно должно быть конечным или даже счетным. Например, полуавтоматы лежат в основе концепции квантовых конечных автоматов . Там набор состояний Q задается комплексным проективным пространством $\mathbb {C} P^{n}$ а отдельные состояния называются с n -состояниями кубитами . Переходы между состояниями задаются унитарными размера n × n матрицами . Входной алфавит $\Sigma$ остается конечным, и другие типичные проблемы теории автоматов остаются в силе. Таким образом, квантовый полуавтомат можно просто определить как тройку $(\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})$ когда алфавит $\Sigma$ имеет p букв, так что существует одна унитарная матрица $U_{\sigma }$ за каждую букву $\sigma \in \Sigma$ . Сформулированный таким образом, квантовый полуавтомат имеет множество геометрических обобщений. , например, Так вместо $\mathbb {C} P^{n}$ , и выборки из его группы изометрий в качестве функций перехода.

Синтаксический моноид регулярного языка изоморфен принимающего моноиду переходов минимального автомата, этот язык.

Литература

А. Х. Клиффорд и Г. Б. Престон , Алгебраическая теория полугрупп . Американское математическое общество, том 2 (1967), ISBN 978-0-8218-0272-4 .
Ф. Гечег и И. Пик, Алгебраическая теория автоматов (1972), Академический Киадо, Будапешт.
WML Холкомб, Алгебраическая теория автоматов (1982), издательство Кембриджского университета
Дж. М. Хоуи , Автоматы и языки , (1991), Clarendon Press, ISBN 0-19-853442-6 .
Мати Килп, Ульрих Кнауэр, Александр В. Михалов, Моноиды, действия и категории (2000), Вальтер де Грюйтер, Берлин, ISBN 3-11-015248-7 .
Рудольф Лидл и Гюнтер Пильц, Прикладная абстрактная алгебра (1998), Springer, ISBN 978-0-387-98290-8

Ссылки

^ Могбели-Дамане, Халиме (июль 2020 г.). «Симметричная моноидальная замкнутая категория cpo M-множеств» (PDF) . Категории и общие алгебраические структуры с приложениями . 13 (1).

[1] Могбели-Дамане, Халиме (июль 2020 г.). «Симметричная моноидальная замкнутая категория cpo M-множеств» (PDF) . Категории и общие алгебраические структуры с приложениями . 13 (1).

[1]