Полуавтомат - Semiautomaton

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

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

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

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

Основная статья: полугрупповое действие

А полугруппа преобразований или моноид преобразования пара ${displaystyle (M, Q)}$ состоящий из набор Q (часто называемый "набором состояния ") и полугруппа или моноид M из функции, или "преобразования", отображение Q себе. Они являются функциями в том смысле, что каждый элемент м из M это карта ${displaystyle mcolon Q o Q}$. Если s и т являются двумя функциями полугруппы преобразований, их полугрупповой продукт определяется как их функциональная композиция ${displaystyle (st) (q) = (scirc t) (q) = s (t (q))}$.

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

M-акты

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

${displaystyle mu двоеточие Q imes M o Q}$

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

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

${displaystyle q1 = q}$

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

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

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

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

${displaystyle mu двоеточие M imes Q o Q}$

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

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

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

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

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

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

Для двух M-акты ${displaystyle Q_ {M}}$ и ${displaystyle B_ {M}}$ разделяя один и тот же моноид ${displaystyle M}$, M-гомоморфизм ${displaystyle fcolon Q_ {M} o B_ {M}}$ это карта ${displaystyle fcolon Q o B}$ такой, что

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

для всех ${displaystyle qin Q}$ и ${displaystyle min M}$. Набор всех M-гомоморфизмы обычно записываются как ${displaystyle mathrm {Hom} (Q_ {M}, B_ {M})}$ или ${displaystyle mathrm {Hom} _ {M} (Q, B)}$.

В M-акты и M-гомоморфизмы вместе образуют категория называется M-Действовать.

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

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

${displaystyle Tcolon Q imes Sigma o Q.}$

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

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

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

За каждое слово ш в ${displaystyle Sigma ^ {*}}$, позволять ${displaystyle T_ {w} двоеточие Q o Q}$ - функция, определенная рекурсивно следующим образом, для всех q в 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 vin Sigma ^ {*}}$, тогда ${displaystyle T_ {w} (q) = T_ {v} (T_ {sigma} (q))}$.

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

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

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

Свойства

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

Набор состояний Q не обязательно быть конечным или даже счетным. Например, полуавтоматы лежат в основе концепции квантовые конечные автоматы. Там множество состояний Q даны сложное проективное пространство ${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}}$, и выборки из его группы изометрии как переходные функции.

В синтаксический моноид из формальный язык является изоморфный к переходному моноиду минимальный автомат принимая язык.

использованная литература

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