編譯原理中的fa是什麼

『壹』 編譯原理中的dfa是什麼意思，是什麼術語的縮寫

DFA(確定性有限自動機)

其實就是有限自動機，deterministic finite automaton

其實我記得好像是詞義分析階段用到的一個技術。。。

『貳』 編譯原理，如何判斷一個FA是DFA還是NFA

DFA或NFA是對計算機程序的行為的抽象模型.你編寫的程序其實就對應了一個自動機.簡單舉例來說,如果a,b可以取值0或1; 程序：if(a==1) b=1; 這個程序對應了一個自動機.
對應的自動機就有狀態 (0,0),(0,1),(1,1),(1,0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時,運行程序的下一個狀態就是(1,1).
畫圖出來就是 這4個狀態作為頂點,並且有下面幾條邊
(0,0) --> (0,0)（自環）,(1,0)-->(1,1),(1,1)-->(1,1)（自環）,(0,1)-->(0,1)自環
存在的意義就是一種理論模型,也可以認為是一種編程思想.詞法分析系也離不開 if else,這一系列的if else和條件也就組成自動機.
最經典體現自動機思想的演算法就是KMP演算法,你肯定學過,字元串子串匹配的演算法.回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機!演算法第二步將原串作為自動機輸入,自動機的輸出就是匹配到的子串位置或者無匹配.

『叄』 【編譯原理】第三章：詞法分析

語言
正則表達：

正則表達式可以由較小的正則表達式遞歸構建。每個正則表達式r定一個語言記作L(r)。

正則表達式優先順序為：克林閉包>連接>或。

簡單來說就是重定義。
例如：
letter -> 字母
number -> 數
d -> 整數

系統根據 當前狀態 與 當前的輸入信息 決定 後繼行為 。
每當處理完當前輸入後，狀態也發生改變。

如果給定輸入串x，如果存在對於該串 從初始狀態到某個終止狀態 的轉換序列，則該串被該FA 接收 。

例：對於FA

abbaabb 是被接收的，而 abbaaba 則不被接收。

重點： 轉換表 ；
一個有窮自動機可以由轉換表表示。

例：

以上兩種自動機都可以用正則表達式 來表示。
事實上， 正則表達式與有窮自動機是等價的 。

從人的角度看，NFA比DFA更加直觀；但對於程序來說，DFA比NFA容易實現。

直接從RE轉換到DFA是比較困難的，所以一般通過NFA作為中介。

DFA中的每個狀態都是NFA中狀態集合的一個子集。

即，先寫出NFA的轉換表，再通過新的狀態構建出DFA。

例：

記數字為 ，字母為 ，那麼標識符的正則表達式為：

這個正則表達式轉換為NFA，表示如下：

這個NFA同時也是一個DFA，所以不用再進行轉換。

記：
數字
數字串
小數部分
指數部分
數

即一個數由一個數字串+可選的小數部分+可選的指數部分構成。
轉換為NFA，表示如下：

通過子集構造法，將NFA轉換為DFA：

可以表示10進制、8進制、16進制的DFA：

『肆』 編譯原理，如何判斷一個FA是DFA還是NFA

第一個是NFA 第二個是DFA
主要區別
1）DFA沒有輸入空串之上的轉換動作；
2）對於DFA，一個特定的符號輸入，有且只能得到一個狀態，而NFA就有可能得到一個狀態集；