Полуавтомат

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

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

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

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

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

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

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

М-акты

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

${\displaystyle \mu \colon Q\times M\to Q}$

${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

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

${\displaystyle q1=q}$

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

${\displaystyle q(st)=(qs)t}$

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

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

${\displaystyle \mu \colon M\times Q\to Q}$

${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

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

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

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

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

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

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

${\displaystyle f(qm)=f(q)m}$

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

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

Полуавтоматы

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

${\displaystyle T\colon Q\times \Sigma \to Q.}$

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

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

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

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

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

Пусть будет набор ${\displaystyle M(Q,\Sigma ,T)}$

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

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

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

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

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

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

Литература

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

Ссылки

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