确定有限状态自动机

✍ dations ◷ 2025-07-07 08:06:58 #确定有限状态自动机

在计算理论中,确定有限状态自动机或确定有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表 Σ {displaystyle Sigma } 的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。

确定有限状态自动机 A {displaystyle {mathcal {A}}} 是由

所组成的5-元组。因此一个DFA可以写成这样的形式: A = ( Q , Σ , δ , s , F ) {displaystyle {mathcal {A}}=left(Q,Sigma ,delta ,s,Fright)}

确定有限状态自动机从起始状态开始,一个字符接一个字符地读入一个字符串 w Σ {displaystyle win Sigma ^{*}} (这里的 {displaystyle {}^{*}} 指示Kleene星号算子。),并根据给定的转移函数一步一步地转移至下一个状态。在读完该字符串后,如果该自动机停在一个属于F的接受状态,那么它就接受该字符串,反之则拒绝该字符串。

为了在保证严谨的前提下,方便地叙述关于DFA的内容,我们定义如下扩展的转移函数:

对于一个确定有限状态自动机 A = ( Q , Σ , δ , s , F ) {displaystyle {mathcal {A}}=left(Q,Sigma ,delta ,s,Fright)} ,如果 δ ( s , w ) F {displaystyle delta ^{*}left(s,wright)in F} ,我们就说该自动机接受字符串w,反之则表明该自动机拒绝字符串w。

被一个确定有限自动机接受的语言(或者叫“被识别的语言”)定义为: L ( A ) = { w Σ | A   {displaystyle {mathcal {L}}({mathcal {A}})={win Sigma ^{*}|{mathcal {A}}~} 接受字符串   w } {displaystyle ~w}} ,也就是由所有被接受的字符串组成的集合。

除了数学上的严谨表述,通常为了讨论方便,也使用状态图直观地表示DFA。不难发现,对于一个给定的DFA,存在唯一一个对应的有向图(但是严格意义上一个有向图不能确定出唯一一个DFA)。有向图的每个结点对应一个状态,每条有向边对应一种转移。习惯上将结点画成两个圈表示接受状态,一个圈表示拒绝状态。用一条没有起点的边指向起始状态。

除了在表述上方便以外,在研究某些问题(如“给定的DFA的语言是否为无穷集合”)时,状态图也提供了有效的解法。

DFA是一种实际的计算模型,因为有平凡的线性时间、恒定空间的在线算法模拟在输入流上的DFA。给定两个DFA有有效算法找到识别它们所识别语言的并集、交集和补集的DFA。还有有效算法确定一个DFA是否接受任何给定字符串,一个DFA是否接受所有字符串,两个DFA是否识别同样的语言,和对特定正则语言找到状态数目最小的DFA(最小DFA)。

在另一方面,DFA在可识别的语言上有严格的限制—很多简单的语言,包括需要多于恒定空间来解决的任何问题,不能被DFA识别。经典的DFA不能识别的简单语言的例子是括号语言,就是由正确配对的括号组成的语言,比如 (()())。由形如anbn的字符串组成的语言,就是有限数目个a,随后是相等数目个b。可以证明没有DFA有足够状态来识别这种语言(通俗地说,因为需要至少2n个状态,而n是不恒定的)。

下面是一个确定有限状态自动机的例子。

确定有限状态自动机 A = ( Q , Σ , δ , s , F ) {displaystyle {mathcal {A}}=left(Q,Sigma ,delta ,s,Fright)}

状态 S 1 {displaystyle S_{1}} 表示在输入的字符串中有偶数个0,而 S 2 {displaystyle S_{2}} 表示有奇数个0。在输入中1不改变自动机的状态。当读完输入的字符串的时候,状态将显示输入的字符串是否包含偶数个0。

A {displaystyle {mathcal {A}}} 能识别的语言是 L ( A ) = { w | # 0 ( w ) 0   ( m o d   2 ) } {displaystyle {mathcal {L}}({mathcal {A}})={w|#_{0}(w)equiv 0~(mod~2)}} 。用正则表达式表示为: ( 1 ( 01 0 ) ) {displaystyle (1^{*}(01^{*}0)^{*})^{*}}

确定有限状态自动机的交,并,差,补,连接,替换,同态,逆同态等运算是封闭的,也就是说确定有限状态自动机通过这些运算产生的新的自动机也是确定有限状态自动机。

A = ( Q , Σ , δ , s , F ) {displaystyle {mathcal {A}}=(Q,Sigma ,delta ,s,F)} 是一个DFA,那么由补运算产生的新DFA定义为: A ¯ = ( Q , Σ , δ , s , Q F ) {displaystyle {bar {mathcal {A}}}=(Q,Sigma ,delta ,s,Q-F)} 。显然只要将 A {displaystyle {mathcal {A}}} 中接受的状态设为不接受的状态,同时把不接受的状态设为接受的状态就得到 A ¯ {displaystyle {bar {mathcal {A}}}} 。补运算的复杂度是: O ( | Q | ) {displaystyle O(left|Qright|)}

有两个DFA, A 1 = ( Q 1 , Σ , δ 1 , s 1 , F 1 ) {displaystyle {mathcal {A}}_{1}=(Q_{1},Sigma ,delta _{1},s_{1},F_{1})} A 2 = ( Q 2 , Σ , δ 2 , s 2 , F 2 ) {displaystyle {mathcal {A}}_{2}=(Q_{2},Sigma ,delta _{2},s_{2},F_{2})} ,那么由这两个DFA创造出来的新的自动机定义为: B = ( Q 1 × Q 2 , Σ , δ B , ( s 1 , s 2 ) , M ) {displaystyle {mathcal {B}}=(Q_{1}times Q_{2},Sigma ,delta _{mathcal {B}},(s_{1},s_{2}),M)} 。其中 M Q 1 × Q 2 {displaystyle Msubseteq Q_{1}times Q_{2}} ( s 1 , s 2 ) {displaystyle left(s_{1},s_{2}right)} B {displaystyle {mathcal {B}}} 的开始状态, δ B {displaystyle delta _{mathcal {B}}} B {displaystyle {mathcal {B}}} 的转移函数,且作如下定义: q 1 Q 1 ,   q 2 Q 2 ,   σ Σ : δ B ( ( q 1 , q 2 ) , σ ) = ( δ 1 ( q 1 , σ ) , δ 2 ( q 2 , σ ) ) {displaystyle forall q_{1}in Q_{1},~q_{2}in Q_{2},~sigma in Sigma :delta _{mathcal {B}}((q_{1},q_{2}),sigma )=(delta _{1}(q_{1},sigma ),delta _{2}(q_{2},sigma ))}

交运算和并运算的复杂度都是 O ( | Q 1 | | Q 2 | | Σ | ) {displaystyle O(left|Q_{1}right|left|Q_{2}right|left|Sigma right|)}

一个同态函数 h : Σ Γ {displaystyle h:Sigma ^{*}rightarrow Gamma ^{*}} 可以递归的定义为:

于是则有   h ( u v ) = h ( u ) h ( v ) {displaystyle ~h(uv)=h(u)h(v)} 。(以上所述中   ϵ {displaystyle ~epsilon } 为空字符,   u , v Σ , σ Σ {displaystyle ~u,vin Sigma ^{*},sigma in Sigma }

此外替换运算和逆同态运算的方法近似。

对于一个正则语言,接受该语言的等价类自动机是一个   ( Q , Σ , δ , s , F ) {displaystyle ~(Q,Sigma ,delta ,s,F)} 的5-元组。其定义如下:

~L被称为Nerode关系,是Myhill-Nerode定理的基础。简单的来说就是对于任意   x , y , z Σ {displaystyle ~x,y,zin Sigma ^{*}} ,如果 x z L y z L {displaystyle xzin LLeftrightarrow yzin L} ,那么x~Ly。

对于任意给定的确定有限状态自动机都能找到一个与之计算能力等价的最小确定有限状态自动机,简称最小自动机。该最小自动机中状态的数量等于能识别相同语言的等价类自动机中等价关系的数量,我们可以称最小自动机和等价类自动机“实际上”是相等的,也就是同构。非正式的说法是:对于最小自动机上的任意状态都可以通过一个同构函数变换成等价类自动机上的一个状态。

能识别一个正则语言的等价类自动机是唯一的,因此能识别该语言的最小自动机也是唯一的。

定义一个非等价关系: N := { ( p , q )   |   p , q Q , w Σ : δ ( p , w ) F δ ( q , w ) F } {displaystyle N:={(p,q)~|~p,qin Q,exists win Sigma ^{*}:delta ^{*}(p,w)in Fleftrightarrow delta ^{*}(q,w)notin F}} ,如下步骤可以得到这个集合N:

以下是由一个任意DFA转换到一个最小DFA的步骤:

这样就得到了接受相同语言的最小自动机。复杂度为 O ( | Q | 2 | Σ | ) {displaystyle O(left|Qright|^{2}left|Sigma right|)}

相关

  • 织机织布机,又称织机,为织造布料的机械。最初的织布机是有梭织布机,后发展出无梭织布机。木制织布机一种脚踏式织布机构造仿古织布机实作纺织
  • 裕华街道裕华街道,是中华人民共和国河北省保定市莲池区下辖的一个乡镇级行政单位。裕华街道下辖以下地区:二中社区、莲池社区、力高社区、环南社区和裕华园社区。
  • 拉什达·琼斯拉什达·琼斯 ( /rəˈʃiːdə/ ; 出生于1976年2月25日) 是美国女演员、导演、作家和制片人。 琼斯出生于加利福尼亚州的洛杉矶,她的父母分别是Quincy Jones和Peggy Lipton
  • 那不勒斯和西西里的利奥波多那不勒斯和西西里的利奥波多(意大利语:,1790年7月2日—1851年3月10日),萨莱诺亲王,两西西里国王费迪南多一世的第六子(五个哥哥中只有法兰西斯科存活,因此形同次子)。1816年,利奥波多
  • 林凤 (明郑)林凤,明末福建龙溪人,为郑成功的部将。林凤年少即强壮异常,膂力过人,被郑成功所激赏,委任为亲军左戎旗镇副将。1658年(永历十二年)3月(农历,以下同),郑成功召集体魄强健的步卒组成铁甲
  • Somebody (综艺节目)《Somebody》(朝鲜语:썸바디)为韩国Mnet于2018年推出的综艺节目,节目主轴为不限舞蹈种类的10位舞者,寻找舞伴以及真爱的综艺节目。10位舞者将于“暧昧之屋”中合宿一个月,并使用身
  • 贝特洛群岛坐标:.mw-parser-output .geo-default,.mw-parser-output .geo-dms,.mw-parser-output .geo-dec{display:inline}.mw-parser-output .geo-nondefault,.mw-parser-output .geo-multi-punct{display:none}.mw-parser-output .longitude,.mw-parser-output .latitude{white-space:n
  • 夏安·海德夏安·海德(英语:Sian Heder,1977年6月23日-)是美国女编剧,电影导演和制片人。她以编剧和导演奥斯卡最佳影片《乐动心旋律》而闻名,她也夺得奥斯卡最佳改编剧本奖和英国电影电视艺术学院奖最佳改编剧本奖(英语:BAFTA Award for Best Adapted Screenplay),以及评论家选择电影奖最佳改编剧本提名。
  • 二水N19水力发电厂二水N19水力发电厂位于台湾彰化县二水乡,由经济部水利署对外招标,民营企业经一绿能公司得标兴建并营运,该发电厂利用浊水溪集集拦河堰北岸联络渠道,于二水段的第19号跌水工之落差进行水力发电。因应政府再生能源政策,经济部水利署盘点全台各地适合兴建小水力发电厂之场址,其中浊水溪的集集拦河堰分有北岸取水口与南岸取水口,北岸已有民营企业兴建的名间水力发电厂,南岸则有台湾电力公司明潭发电厂浊水机组。其中南北岸分别仍有多处上开发的水力发电潜力场址,经水利署与台湾电力公司协调,南岸联络渠道由台湾电力公司兴建明潭发电厂集集
  • 艾氏欧白鱼艾氏欧白鱼(学名:)是辐鳍鱼纲鲤形目雅罗鱼科欧白鱼属的其中一种。分布于土耳其贝谢伊尔湖,它们栖息在淡水湖,但因失去栖息地而灭绝。该物种体长可达1.5公分。