【導(dǎo)讀】機(jī)之間的相互關(guān)系。要求掌握正則文法、狀態(tài)轉(zhuǎn)換圖、DFA、NFA、正規(guī)式和正規(guī)集的基。等價,而且也等價于一個特殊類型的語言產(chǎn)生器——正規(guī)表達(dá)式。因此許多簡單的程序語言都可由FA所識別。事實(shí)上,它是描述詞法的有效工具,也是。進(jìn)行詞法分析的主要理論基礎(chǔ)。型——有窮自動機(jī)。它的模擬程序可以作為詞法分析程序的控制程序。程序的自動構(gòu)造尋找特殊的方法和工具。K,Z稱為終態(tài)集合,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。(e)f是轉(zhuǎn)換函數(shù),是一個從K×Σ到K的單值映射。kj稱為ki的一個后繼狀態(tài)。DFA的映射關(guān)系可以由一個矩陣表示,矩陣的行標(biāo)表示狀態(tài),列標(biāo)表示輸入字符,Σ,f(k,a)唯一地確定了下一個狀態(tài),從狀態(tài)轉(zhuǎn)換圖來看,若字母表Σ含。達(dá)終止?fàn)顟B(tài),則該輸入串能被該自動機(jī)所接受。NFA的映射是Q×Σ→Q的子集,是一個多值映射,而DFA的映射是Q×Σ→Q,DFA是NFA的特例,對于每個NFAM,存在一個DFAM’,使得L=L(M’)。