Полуавтомат

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

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

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

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

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

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

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

M -acts [ править ]

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

${\ Displaystyle \ му \ двоеточие Q \ раз от M \ до Q}$

${\ Displaystyle (д, м) \ mapsto qm = \ му (д, м)}$

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

${\ displaystyle q1 = q}$

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

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

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

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

${\ displaystyle \ mu \ двоеточие M \ times Q \ to Q}$

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

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

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

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

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

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 -act .

Полуавтоматы [ править ]

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

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

Когда множество состояний Q представляет собой конечное множество, не Б нуждается, semiautomaton можно рассматривать как детерминированный конечный автомат , но без начального состояния или множеств принимают состояния 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 задаются комплексным проективным пространством , и отдельные государства, называются п -state кубитов . Переходы состояний задаются унитарными матрицами размера 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}}$

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

Ссылки [ править ]

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