半自动机 目录 变换半群 Mdisplaystyle M-acts 完全变换幺半群 半自动机 M-同态 性质 范畴Act 引用 导航菜单Associative Digital Network Theory

Multi tool use
Multi tool use

自动机形式语言半群论


数学计算机科学幺半群代数结构群作用自动机范畴论作用函子集合狀態函數幺半群半群函數複合恒等函数幺半群集合结合性字符串字符串运算形式语言自由幺半群置换群确定有限自动机有限状态自动机字母表自由幺半群Kleene星号字符串函数复合恒等函数结合性状态转移表de Bruijn图量子有限自动机复投影空间qubit酉n×n矩阵黎曼对称空间形式语言语法幺半群同构极小自动机范畴对象态射




在数学和计算机科学中,半自动机Mdisplaystyle M-act是幺半群在集合上的乘法性运算。从代数结构的观点来看,它非常接近于群作用的概念。从计算机科学的观点来看,它是只有输入没有输出的自动机。从范畴论的观点来看,作用是如范畴上的函子般重要。


这个概念也叫做S-集合M-集合M-操作数S-系统S-自动机转移系统算子幺半群变换半群转移幺半群。本文力图表现出它们表示的是同一个概念,尽管在使用中有各种概念和术语的变体。




目录





  • 1 变换半群


  • 2 Mdisplaystyle M-acts


  • 3 完全变换幺半群


  • 4 半自动机


  • 5 M-同态


  • 6 性质


  • 7 范畴Act


  • 8 引用




变换半群


變換半群變換幺半群是由集合Qdisplaystyle Q(通常稱為“狀態集合”),和映射Qdisplaystyle Q到自身的函數或“變換”Mdisplaystyle M之幺半群或半群構成的有序对(M,Q)displaystyle (M,Q)。此類函數意指Mdisplaystyle M中的每個元素mdisplaystyle m均為一m:Q→Qdisplaystyle m:Qto Q映射。若sdisplaystyle stdisplaystyle t是這個變換半群的兩個不同函數,則半群乘積可直覺地由函數複合得出,故吾人將(st)(q)displaystyle (st)(q)定義為(s∘t)(q)=s(t(q))displaystyle (scirc t)(q)=s(t(q))


注意“半群”與“幺半群”的使用:有些作者將“半群”與“幺半群”視為同義詞。然而此處一個半群不必然包含單位元素;而一個幺半群則意指含有單位元素的半群。因為作用於集合上的函數概念永遠包括恒等函数概念在內,亦即施加於集合上時不做任何動作,故變換半群可藉由與恒等函數聯集轉為幺半群。



Mdisplaystyle M-acts


Mdisplaystyle M是幺半群而Qdisplaystyle Q是非空集合。如果存在一个乘法运算


μ:Q×M→Qdisplaystyle mu :Qtimes Mto Q
(q,m)↦qm=μ(q,m)displaystyle (q,m)mapsto qm=mu (q,m)


它满足性质


q1=qdisplaystyle q1=q


此處1表幺半群之單位元素,並且


q(st)=(qs)tdisplaystyle q(st)=(qs)t


对所有q∈Qdisplaystyle qin Qs,t∈Mdisplaystyle s,tin M,三元组(Q,M,μ)displaystyle (Q,M,mu )被称为Mdisplaystyle M-act或简稱右-act。一般而言,μdisplaystyle mu 表示“Qdisplaystyle Q的元素与Mdisplaystyle M的元素的右乘法”。右-act经常写为QMdisplaystyle Q_M


左-act定义类似,即


μ:M×Q→Qdisplaystyle mu :Mtimes Qto Q
(m,q)↦mq=μ(m,q)displaystyle (m,q)mapsto mq=mu (m,q)


并经常表示为MQdisplaystyle ,_MQ


一個Mdisplaystyle M-act变换半群十分相似,然而Mdisplaystyle M的元素本身不必然為函数,它们僅是某个幺半群的元素。所以,必须限制μdisplaystyle mu 的作用與幺半群中的乘法一致(亦即,μ(q,st)=μ(μ(q,s),t)displaystyle mu (q,st)=mu (mu (q,s),t)),因为一般而言,对于某个任意μdisplaystyle mu 此性質可能不成立,保證此一致性可使進行函數複合時不致出問題。


一旦加上这种限制,就可以完全放心的去掉所有括号,因为幺半群乘积和幺半群在集合上的作用是完全滿足结合性的。特别是这允许了幺半群的元素被表示为计算机科学意义上字母的字符串。这种抽象接着允许谈论一般的字符串运算,并最终导致了由字母的字符串构成的形式语言概念。


Mdisplaystyle M-act和變換幺半群的另一個差異在於,對一個Mdisplaystyle M-act Qdisplaystyle Q,幺半群的兩個相異元素可能決定同樣的Q變換。若我們限制其發生,則Mdisplaystyle M-act與變換幺半群便完全相同。



完全变换幺半群


完全变换幺半群(或完全变换半群)是所有映射m:Q→Qdisplaystyle m:Qto Q的搜集。完全变换幺半群是自由幺半群,在允许所有可能性的意义上。完全变换幺半群的一个特殊情况是置换群。



半自动机


半自动机是三元组(Q,Σ,T)displaystyle (Q,Sigma ,T),这里的Σdisplaystyle Sigma 是叫做“输入字母表”的非空集合,Q是叫做“状态集合”的非空集合,而T是“转移函数”,


T:Q×Σ→Qdisplaystyle T:Qtimes Sigma to Q

当状态集合Q是有限集合(不是必须的!)的时候,半自动机可以被认为是确定有限自动机(Q,Σ,T,q0,A)displaystyle (Q,Sigma ,T,q_0,A),但是没有“初始状态” q0displaystyle q_0或“接受状态”的集合A。它还可以被认为是没有输出只有输入的有限状态自动机。


幺半群理论的一个主要主张是半自动机等价于act;所以对于任何act,都有一个唯一的半自动机,或反过来说,对于任何半自动机,都有一个唯一的act。这可以如下这样证实。


Σ∗displaystyle Sigma ^*是从字母表Σdisplaystyle Sigma 生成的自由幺半群,(上标* 要被理解为是Kleene星号);它是由在Σdisplaystyle Sigma 中字母构成的所有有限长度字符串的集合。


对于所有Σ∗displaystyle Sigma ^*中的字w,设Tw:Q→Qdisplaystyle T_w:Qto Q是如下递归定义的函数,对于所有Q中的q:


  • 如果w=εdisplaystyle w=varepsilon ,则Tε(q)=qdisplaystyle T_varepsilon (q)=q,所以空字εdisplaystyle varepsilon 不改变状态。
  • 如果w=σdisplaystyle w=sigma Σdisplaystyle Sigma 中的字母,则Tσ(q)=T(q,σ)displaystyle T_sigma (q)=T(q,sigma )
  • 如果w=σvdisplaystyle w=sigma v对于σ∈Σdisplaystyle sigma in Sigma v∈Σ∗displaystyle vin Sigma ^*,则Tw(q)=Tv(Tσ(q))displaystyle T_w(q)=T_v(T_sigma (q))

M(Q,Σ,T)displaystyle M(Q,Sigma ,T)是个集合


M(Q,Σ,T)=Twdisplaystyle M(Q,Sigma ,T)=T_wvert win Sigma ^*

集合M(Q,Σ,T)displaystyle M(Q,Sigma ,T)在函数复合下闭合;就是说,对于所有v,w∈Σ∗displaystyle v,win Sigma ^*,有着Tw∘Tv=Tvwdisplaystyle T_wcirc T_v=T_vw。它还包含Tεdisplaystyle T_varepsilon ,它是S上的恒等函数。因为函数复合根据定义是结合性的,集合M(Q,Σ,T)displaystyle M(Q,Sigma ,T)是幺半群:它叫做半自动机(Q,Σ,T)displaystyle (Q,Sigma ,T)输入幺半群特征幺半群特征半群转移幺半群



M-同态


M-同态是映射


f:QM→BMdisplaystyle f:Q_Mto B_M

使得


f(qm)=f(q)mdisplaystyle f(qm)=f(q)m

对于所有q∈Qdisplaystyle qin Qm∈Mdisplaystyle min M。所有M-同态的集合通常写为Hom(QM,BM)displaystyle mathrm Hom (Q_M,B_M)HomM(Q,B)displaystyle mathrm Hom _M(Q,B)



性质


如果状态集合Q是有限的,则转移函数通常表示为状态转移表。在自由群中字符串所驱动的所有可能转移的构造有一种叫de Bruijn图的图形描述。


状态集合Q不需要是有限的。作为例子,半自动机巩固了量子有限自动机的概念。它的状态集合Q由复投影空间CPndisplaystyle mathbb C P^n给出,单独状态别称为n-状态qubit。状态转移给出自酉n×n矩阵。输入字母表Σdisplaystyle Sigma 仍是有限的,而其他自动机理论的典型关键概念仍有效。因此,量子半自动机可简单的定义为三元组(CPn,Σ,Uσ1,Uσ2,⋯,Uσp,)displaystyle (mathbb C P^n,Sigma ,U_sigma _1,U_sigma _2,cdots ,U_sigma _p,)当字母表Σdisplaystyle Sigma p个字母的时候,所以对每个字母σ∈Σdisplaystyle sigma in Sigma 都有一个酉矩阵Uσdisplaystyle U_sigma 。这种方式规定之后,量子半自动机明显有多种几何推广。比如,可以用黎曼对称空间替代CPndisplaystyle mathbb C P^n,并从它的等距群选出转移函数。


形式语言的语法幺半群同构于到接受这个语言的极小自动机的转移幺半群。



范畴Act


定义右作用的代数关系形成了一个范畴Act。对象是M-act,而范畴的态射是M-同态。



引用


  • John M. Howie, Fundamentals of Semigroup Theory(1995), Clarendon Press, Oxford ISBN 0-19-851194-9

  • Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories(2000), Walter de Gruyter, Berlin ISBN 3-11-015248-7

  • A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups. American Mathematical Society,(1961)volume 1,(1967)volume 2.

  • F. Gecseg and I. Peak, Algebraic Theory of Automata(1972), Akademiai Kiado, Budapest.


  • Nico F. Benschop, Associative Digital Network Theory[永久失效連結] An Associative Algebra Approach to Logic, Arithmetic and State Machines(2003)Amspade Research, Geldrop, The Netherlands.


Lza,AH8 hvr4XrqO NB561lIqHJ scn2
3VwqPTs7 xD3J,Uoa FiD9O

Popular posts from this blog

名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

香港授勳及嘉獎制度 目录 勳章及獎狀類別 嘉獎等級 授勳及嘉獎提名 統計數字 多次獲頒勳章或獎狀的人士 爭議 褫奪機制 参考文献 外部連結 参见 导航菜单統計數字一九九七年七月二日(星期三)香港特別行政區的授勳制度六七暴動領袖獲大紫荊勳章 董建華被斥為肯定殺人放火董建華授勳楊光 議員窮追猛打蘋論:顛倒是非黑白的大紫荊董讚楊光有貢獻避談暴動董拒答授勳楊光原因撤除勳銜撤除勳銜撤除勳銜特首掌「搣柴」生殺權行為失當罪 隨時「搣柴」失長糧政府刊憲 許仕仁郭炳江遭「搣柴」去年中終極上訴失敗 許仕仁郭炳江撤勳章太平紳士猛料阿Sir講古—— 「搣柴」有故一九九八年授勳名單一九九九年授勳名單二○○三年授勳名單二○○八年授勳名單二○○七年授勳名單政府總部禮賓處 - 授勳及嘉獎香港特別行政區勳章綬帶一覽(PDF)(非官方)

Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar