确定有限状态自动机

✍ dations ◷ 2025-07-08 16:48:05 #确定有限状态自动机

在计算理论中,确定有限状态自动机或确定有限自动机(英语: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|)}

相关

  • 萨克岛萨克岛(英语:Sark;法语:Sercq(cq不发音)/ 萨克语:Sèr)是位于英吉利海峡中,是海峡群岛的一个岛屿,属于英国拥有宗主权的根西行政区(Bailiwick of Guernsey)管辖。2002年时萨克岛人口为61
  • 七略《七略》,中国第二部国家藏书目录。汉朝宗室刘向、刘歆父子整理图书近20年,编纂《别录》20卷,成书后,刘歆又将其节略成《七略》7卷。二书对中国后世史学与目录学皆有重大影响。
  • 月光光心慌慌)是一部于1978年上映的美国恐怖电影,为“月光光心慌慌系列电影(英语:Halloween (franchise))”的首部曲。约翰·卡本特执导及编剧,同时他也身任配乐的工作。唐纳德·普莱森斯与杰
  • 阿图尔·德·赫里夫阿图尔·德·赫里夫(荷兰语:Arthur De Greef,1862年10月10日-1940年8月29日),比利时弗拉芒钢琴家,作曲家。早年在布鲁塞尔音乐学院学习,后赴魏玛师从李斯特,成为一名出色的钢琴演奏家
  • 徐道焜徐道焜(1848年-?),号仲文,江西省吉水县人,清朝政治人物、进士出身。同治九年,优贡生。光绪元年,江西乡试中举。光绪三年,登进士,改翰林院庶吉士。光绪六年,任工部候补主事。光绪十八年,任
  • 北浦和站北浦和站(日语:北浦和駅/きたうらわえき  */?)位于日本埼玉县埼玉市浦和区北浦和(日语:北浦和)三丁目,是东日本旅客铁道(JR东日本)的铁路车站。此站停靠的路线名称是东北本线(详情参
  • 库珀群岛库珀群岛(英语:Cooper Islands)是美国的群岛,位于阿图岛东北面1.6公里的白令海,属于尼尔群岛的一部分,由阿拉斯加州负责管辖,群岛上无人居住。
  • 汤浅谦汤浅谦(1916年10月23日-2010年11月2日),是第二次世界大战时的一名日本军医,出生于埼玉县,在日本侵华时期曾对中国战俘进行活体解剖。英国广播
  • 埃里温地铁.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none;width:100%;margin:0;border:none}.mw-parser-output table.routemap{padding:0;border:0;border-col
  • 拜奈代克·蒂博尔拜奈代克·蒂博尔(匈牙利语:Benedek Tibor,1972年7月12日-2020年6月18日),匈牙利男子水球运动员。他曾代表匈牙利参加1992年、1996年、2000年、2004年和2008年夏季奥林匹克运动会水球比赛,共获得三枚金牌。