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