세미우토마톤

수학 및 이론 컴퓨터 과학에서 반유토마톤은 입력은 있지만 출력은 없는 결정론적 유한 자동이다.상태의 집합 Q, 입력 알파벳이라 불리는 집합 σ, 전환함수라 불리는 함수 T: Q × σ → Q로 구성된다.

어떤 반유토마톤과 연관되어 있는 것은 상태 Q의 집합에 작용하는 반유토마톤의 특성 모노이드, 입력 모노이드, 전이 모노이드 또는 전이 시스템이라고 불리는 단조형이다.이것은 입력 문자 Ⅱ에서 문자열의 자유 단모형의 작용으로 볼 수도 있고 Q의 유도 변환 세미그룹으로 볼 수도 있다.

클리포드와 프레스턴(1967)과 같은 오래된 책에서는 S-acts를 "operands"라고 부른다.

카테고리 이론에서 세미우토마타는 본질적으로 펑커다.

변환 세미그룹 및 모노이드 동작

주요기사:세미그룹작업

변환 세미그룹이나 변환 모노이드$($moid)는 집합 Q$($흔히 "상태의 집합"이라고 불림)와 함수의 세미그룹이나 모노이드 M($transformation$)으로 구성되는$$ 쌍$(M$, Q ${\displaystyle )}$이다.They are functions in the sense that every element m of M is a map ${\displaystyle m\colon Q\to Q}$. If s and t are two functions of the transformation semigroup, their semigroup product is defined as their function composition ${\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}$.

일부 저자들은 "세미그룹"과 "모노이드"를 동의어로 여긴다.여기서 세미그룹은 정체성 요소를 가질 필요가 없다; 모노이드(monoid)는 정체성 요소("단위"라고도 함)를 가진 세미그룹이다.집합에 작용하는 기능의 개념은 항상 ID 함수의 개념을 포함하기 때문에, 집합에 적용했을 때 아무것도 하지 않기 때문에, ID 함수를 추가하여 변환 세미그룹을 모노이드로 만들 수 있다.

M-acts

M은 모노이드로, Q는 비어 있지 않은 세트로 하자.승법 연산이 있는 경우

$\displaystyle \mu \colon Q\time M\to Q}$

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

성질을 만족시키는 것

${\displaystyle q1=q}$

1 단위의 모노이드와

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

모든 $q{\displaystyle q}$ ${\displaystyle q\in Q}$ $및$ s${\displaystyle ,}$ ${\displaystyle t}$ ${\displaystyle \in }$ ${\displaystyle M}$ ${\displaystyle s,t\in M}$에 대해$,$ 3중$({\displaystyle Q}$, ${\displaystyle M}$, ${\displaystyle \mu }$) ${\displaystyle (Q,M,\mu$)은 오른쪽 M-act 또는 단순히 옳은 행위라고 불린다$$.장기적으로는 $\mu {\displaystyle }$ ${\displaystyle \mu }$이(가) Q의 원소를 M의 원소에 의해 적절히 곱한 것이다$$.올바른 행동은 $종종{\displaystyle {}_{}}$ Q ${\displaystyle M_{}}$ ${\$로 쓰여진다$.$

좌익행위는 다음과 같이 정의된다.

$\displaystyle \mu \colon M\time Q\to Q}$

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

${\displaystyle {}_{}}$ 종종 ${\displaystyle {}_{}}$ Q ${\displaystyle \,_{$M}$Q}$로 표시된다$.$

M-act는 단조로운 변환과 밀접하게 관련되어 있다.그러나 M의 요소들은 각각의 기능이 될 필요는 없고 단지 어떤 모노이드의 요소일 뿐이다.Therefore, one must demand that the action of ${\displaystyle \mu }$ be consistent with multiplication in the monoid (i.e. ${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$), as, in general, this might not hold for some arbitrary ${\displaystyle \mu }$, in the way that it does for function c광각의

일단 이런 요구를 하게 되면, 모노이드 제품과 세트 상의 모노이드의 작용이 완전히 연상되기 때문에, 모든 괄호를 떨어뜨리는 것은 완전히 안전하다.특히, 이것은 "끈"이라는 단어의 컴퓨터 과학적인 의미에서 단조로운 요소들을 문자의 문자열로 나타낼 수 있게 한다.그러면 이 추상화는 일반적으로 문자열 연산에 대해 이야기할 수 있게 하고, 결국 문자열을 구성하는 형식 언어의 개념으로 이어진다.^{[further explanation needed]}

M-act와 변환 모노이드의 또 다른 차이점은 M-act Q의 경우, 모노이드의 두 개별 요소가 Q의 동일한 변환을 결정할 수 있다는 것이다.만약 우리가 이런 일이 일어나지 않도록 요구한다면, M-act는 본질적으로 변형 단면체와 동일하다.

M-호모형성

For two M-acts ${\displaystyle Q_{M}}$ and ${\displaystyle B_{M}}$ sharing the same monoid ${\displaystyle M}$, an M-homomorphism ${\displaystyle f\colon Q_{M}\to B_{M}}$ is a map ${\displaystyle f\colon Q\to B}$ such that

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

for all ${\displaystyle q\in Q_{M}}$ and ${\displaystyle m\in M}$. The set of all M-homomorphisms is commonly written as ${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$ or ${\displaystyle \mathrm {Hom} _{M}(Q,B)}$.

M-acts와 M-homorphism은 함께 M-Act라는 범주를 형성한다.

세미우토마타

$반자동$은 트리플$({\displaystyle }$Q${\displaystyle }$, ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle T}$) ${\displaystyle (Q$$,\$$Sigma$ ,T)이며$,$ 여기서 $}$ {\$displaystyle \Sigma}}$은 입력 알파벳이라 불리는 비빈 집합이고, Q는 상태 집합이라 불리는 비빈 집합이며, T는 전환 함수다.

$\displaystyle T\colon Q\time \Sigma \to Q.}$

When the set of states Q is a finite set—it need not be—, a semiautomaton may be thought of as a deterministic finite automaton ${\displaystyle (Q,\Sigma ,T,q_{0},A)}$, but without the initial state ${\displaystyle q_{0}}$ or set of accept states A.또는 출력이 없고 입력만 있는 유한 상태 기계다.

어떤 반유토마톤도 다음과 같은 방법으로 모노이드의 행위를 유도한다.

$\sigma {\displaystyle {\mathrm{}}^{}}$ $∗$ {\$displaystyle \Sigma$^{*}} $알파벳{\displaystyle \mathrm{}}$ $\$ {\$displaystyle \Sigma }$에 생성되는 자유 모노이드(위첨자 *가 클라인 별로 이해되도록 함)$$로$$ 한다. $\sigma {\displaystyle \mathrm{}}$ ${\displaysty \Sigma }$의 문자로 구성된 모든 유한 길이 문자열의 집합이다$.$

${\displaystyle {\ast }^{}}$ ${\$의 w 단어마다 T $w{\displaystyle {}_{}}$: ${\displaystyle Q}$→ ${\displaystyle Q}$ ${\displaystyle T_{w}\colon Q\to Q}$의 모든 Q에 대해 다음과 같이 반복적으로 정의된 함수가 되도록 한다$$$.$

• $w{\displaystyle }$= ${\displaystyle \epsilon }$ ${\displaystyle w=\varepsilon$ $\},$ $t{\displaystyle {}_{}}$ ${\displaystyle {\epsilon }_{}}$(${\displaystyle q}$ ${\displaystyle )}$= ${\displaystyle q}$ = q = ${\displaystyle T_{\varepsilon }(q)=q$ 그래서 빈 단어 $\epsilon {\displaystyle }$ ${\displaysty \varepsilon }$이 상태를 변경하지 않는다$$.
• $w{\displaystyle }$= $\sigma {\displaystyle \mathrm{}}$ ${\$$displaystyle$ w$=\$$sigma }$의 문자인$$ 경우$,$ $T{\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}}$ (${\displaystyle }$q${\displaystyle }$) = ${\displaystyle T}$ ( ${\displaystyle q,}$ ${\displaystyle q}$) ${\displaystyle T_{\sigma }(q,\sigma$ $)\}.$
• If ${\displaystyle w=\sigma v}$ for ${\displaystyle \sigma \in \Sigma }$ and ${\displaystyle v\in \Sigma ^{*}}$, then ${\displaystyle T_{w}(q)=$$T_{v}(T_{\sigma }(q$

$Let{\displaystyle }$ M${\displaystyle }$( ${\displaystyle Q}$, ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle T}$) ${\displaystyle M(Q,\Sigma ,T)$을 세트로$$ 한다.

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

The set ${\displaystyle M(Q,\Sigma ,T)}$ is closed under function composition; that is, for all ${\displaystyle v,w\in \Sigma ^{*}}$, one has ${\displaystyle T_{w}\circ T_{v}=T_{vw}}$. It also contains ${\displaystyle T_{\varepsilon }}$, which is the identQ에서 ity 기능.Since function composition is associative, the set ${\displaystyle M(Q,\Sigma ,T)}$ is a monoid: it is called the input monoid, characteristic monoid, characteristic semigroup or transition monoid of the semiautomaton ${\displaystyle (Q,\Sigma ,T)}$.

특성.

상태 Q의 집합이 유한하면, 전환 기능은 일반적으로 상태 전환 표로 표현된다.자유 모노이드의 끈에 의해 구동되는 모든 가능한 전환의 구조는 드 브루옌 그래프로서 그래픽으로 묘사된다.

상태 Q의 집합은 유한하거나 심지어 셀 수 있는 것이 아니다.예를 들어, 세미우토마타는 양자 유한 자동화의 개념을 뒷받침한다.여기서 상태 Q의 집합은 복합 투영 공간 C ${\displaystyle P^{}}$ n ${\$ P$^{n}}$에 의해 주어지며$,$ 개별 상태를 n-상태 Qubit라고 한다.상태 전환은 단일 n×n 행렬에 의해 주어진다.입력 문자 ${\displaystyle \Sigma }$은 유한한$$ 상태를 유지하며, 오토마타 이론의 다른 일반적인 우려는 여전히 유효하다.Thus, the quantum semiautomaton may be simply defined as the triple ${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}},\})}$ when the alphabet ${\displaystyle \Sigma }$ has p letters, so that there is one unateral ${\displaystyle {matrix}_{}}$ $U{\displaystyle {}_{}}$ $∈{\$ 각 문자$$ ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \in }$ ∈ { { { { { { $\sigma \in \Sigma$ $\}\}.$ 이렇게 표현된 퀀텀 세미아우토마톤은 기하학적 일반화가 많다.따라서 예를 들어, ${\displaystyle C{}^{}}$ P ${\displaystyle n^{}}$ ${\$ P$^{n$ 대신 리만 대칭 공간을 사용할 수 있으며, 전환 함수로 이등분계 그룹에서 선택할 수 있다.

정규 언어의 통사적 단모형은 언어를 받아들이는 최소 자동화의 전환 단모형에 이형적이다.

참조

• A. H. 클리포드와 G. B. 프레스턴, Semigroups의 대수학 이론.미국수학학회 제2권(1967), ISBN978-0-8218-0272-4.
• F. Gecseg와 나.부다페스트 아카데미 키아도 오토마타의 피크, 대수학 이론(1972년)
• W. M. L. Holcombe, 대수학 오토마타 이론(1982), 케임브리지 대학교 출판부
• J. M. Howie, Automata and Languages, (1991), Clarendon Press, ISBN 0-19-853442-6.
• 마티 킬프, 울리히 크나워, 알렉산더 5세Mikhalov, Monoids, Acts and Categories(2000), Walter de Gruyter, Berlin, ISBN 3-11-015248-7.
• 루돌프 리들 및 귄터 필즈, 응용 추상 대수(1998), 스프링어, ISBN 978-0-387-98290-8