當前位置:首頁 > 芯聞號 > 充電吧
[導讀]Atitit 四種自動機 fsm pda?目錄1. 自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。 21.1. 抽象自動機的理論。 21.2. 自

Atitit 四種自動機 fsm pda

?

目錄

1. 自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。 2

1.1. 抽象自動機的理論。 2

1.2. 自動機就是語言的解釋器?ati總結(jié) 2

1.3. 四種形式語言四種文法對應四種自動機 2

2. 四種自動機 fsm pda lba turin 2

2.1. FSM "finite state machine"有限狀態(tài)自動機(FSM "finite state machine??正則語言機器 2

2.2. 圖靈機模型(無限狀態(tài)的自動機);用來描述通用計算機計算能力的圖靈機模型; 2

2.3. PDA下推自動機;push down automata 3

2.4. LBA線性有界自動機 (linear bounded automaton)上下文有關語言的識別接受器。 3

3. 對語言的識別能力上講:?有限狀態(tài)自動機<非確定下推自動機<線性有界非確定圖靈機<圖靈機(無限狀態(tài)的自動機) 3

4. 其他類型自動機 3

5. 四大文法 4

5.1. 0型文法(對應圖靈機)也稱短語文法,記為PSG。 4

5.2. 1型文法(對應線性界線自動機,自然語言)上下文有關文法,記為CSG。 4

5.3. 2型文法(對應下推自動機,程序設計語言)上下文無關文法,記為CFG。 4

5.4. 3型文法(對應有限自動機)也叫正規(guī)文法,記為RG。 4

6. ref 5

?

?

1.?自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。1.1.?抽象自動機的理論。

抽象自動機是一種能夠識別語言的抽象的裝置,它不是具有物理實體的機器,而是表示計算機運算方式的抽象的邏輯關系系統(tǒng),這樣的抽象自動機可以用來檢驗輸入的符號串是不是語言中合格的句子,如果是合格的句子,自動機就接收它,如果不是,就不接收它。如圖所示:

1.2.?自動機就是語言的解釋器?ati總結(jié)1.3.?四種形式語言四種文法對應四種自動機2.?四種自動機 fsm pda lba turin

?

2.1.?FSM "finite state machine"有限狀態(tài)自動機(FSM "finite state machine??正則語言機器

計算能力

確定有限狀態(tài)自動機與非確定有限狀態(tài)自動機識別的語言都是正則語言。由于正則語言的良好性質(zhì),許多為其他自動機(下推自動機或圖靈機)不能判定的問題,在有限狀態(tài)自動機的情形下,都可以得到判定,并且存在有效的算法。

?

2.2.?圖靈機模型(無限狀態(tài)的自動機);用來描述通用計算機計算能力的圖靈機模型;

圖靈機(無限狀態(tài)的自動機)

2.3.?PDA下推自動機;push down automata

?

2.4.?LBA線性有界自動機 (linear bounded automaton)上下文有關語言的識別接受器。

?

一種圖靈機.是把計算限制在僅僅包含輸人的那一段帶上的圖靈機.可用作上下文有關語言的識別接受器。

線性有界自動機(縮寫為LBA)可形式地由M=<K,}',1',8,qo,F)來表示.其中:K是狀態(tài)的有限集;尸是帶符號的有限集;}}1'是輸人符號集;K中的q。是起始狀態(tài);FcK是終結(jié)狀態(tài)集;8是從KXI'到KXI'X {L,R}子集的映射,<L,R)分別是讀寫頭左右移一格.刃含有兩個特殊的符號,通常記為本和$,它們分別是左端標志和右端標志.這些符號開始就處在輸人帶的端點,其作用是阻止帶頭離開帶上出現(xiàn)符號的區(qū).

3.?對語言的識別能力上講:
有限狀態(tài)自動機<非確定下推自動機<線性有界非確定圖靈機<圖靈機(無限狀態(tài)的自動機)4.?其他類型自動機

由下推表組成的單項非確定程序的下推自動機;

線性有界自動機;

用來描述通用計算機計算能力的圖靈機模型;

進行與轉(zhuǎn)移函數(shù),轉(zhuǎn)移狀態(tài)有關輸出的時序機;

由一些基本語句構(gòu)成程序框圖的波斯特機;隨即存儲機;

堆棧自動機;

不受有限自動機做控制器和存儲限制的無限自動機;

統(tǒng)計自動機某一條件概率分布的概率自動機和細胞自動機。

?

5.?四大文法

一般的文法至少都是0型文法,也就是說0型文法限制最少。若將0型文法比作基類的話,1、2、3型文法就是不斷繼承并加以限制得到的子類。
文法表示過程中,常用大寫字母表示非終結(jié)符VN,而小寫字母表示的是終結(jié)符VT。

?

5.1.?0型文法(對應圖靈機)也稱短語文法,記為PSG。

·?一個非常重要的理論結(jié)果是:0型文法的能力相當于圖靈機?;蛘哒f,任何0型文語言都是遞歸可枚舉的,反之,遞歸可枚舉集必定是一個0型語言。

5.2.?1型文法(對應線性界線自動機,自然語言)上下文有關文法,記為CSG。

·?此文法對應于線性有界自動機。

5.3.?2型文法(對應下推自動機,程序設計語言)上下文無關文法,記為CFG。

·??2型文法也叫上下文無關文法,記為CFG。

·?此文法對應于下推自動機。

?

5.4.?3型文法(對應有限自動機)也叫正規(guī)文法,記為RG。

·?它是在2型文法的基礎上滿足:A→α|αB(右線性)或A→α|Bα(左線性)。

·?3型文法也叫正規(guī)文法,記為RG。

·?此文法對應于有限狀態(tài)自動機。

?


本站聲明: 本文章由作者或相關機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉
關閉