確定有窮自動機的最小化問題探討

文章編號：1672-5913(2008)07-0040-03

摘要：本文針對DFA最小化時可能遇到的各種情形，給出最小化的通用算法，并通過具體實例加以驗證。此算法有利于學生對編譯原理課程中DFA最小化的學習和理解，同時讓學生進一步了解此知識點在其他問題求解中的應(yīng)用。

關(guān)鍵詞：有窮自動機(FA)；確定有窮自動機(DFA)；最小化

中圖分類號：G642

文獻標識碼：B

1引言

詞法分析是編譯程序的第一階段，其實質(zhì)是從描述單詞構(gòu)成的工具——正規(guī)表達式，向識別單詞的工具——確定有限自動機(DFA)的等價轉(zhuǎn)化。此過程包括正規(guī)表達式到非確定有限自動機(NFA)的轉(zhuǎn)化、NFA到確定有限自動機(DFA)的轉(zhuǎn)化和DFA的最小化(化簡)三個環(huán)節(jié)。DFA最小化是轉(zhuǎn)化的最后一步，也是有限自動機應(yīng)用及實現(xiàn)方面的重要研究問題之一。它揭示了狀態(tài)之間的內(nèi)在聯(lián)系，既方便DFA存儲實現(xiàn)，又可以提高自動識別單詞的效率。本文在分析DFA最小化理論的基礎(chǔ)上，針對轉(zhuǎn)化過程中可能出現(xiàn)的各種情形，給出求DFA M的最小化DFA M′的一種通用算法，并給出實例加以驗證。

2DFA最小化理論分析

已知一確定有限自動機DFAM，s和t是M的任意兩個不同的狀態(tài)。DFA最小化問題涉及到以下幾個重要概念：

1) DFA的最小化定義：是指構(gòu)造一個與DFA M等價且狀態(tài)個數(shù)最少的DFA M′，即等價最小DFAM′，有L(M)=L(M′)。

2) 等價狀態(tài)：若從狀態(tài)s出發(fā)能讀出某個字α而停于終態(tài)，從狀態(tài)t出發(fā)也能讀出同一個字α而停于終態(tài)；反之，若從t 出發(fā)能讀出某個字α而停于終態(tài)，則從s出發(fā)也能讀出同一個字α而停于終態(tài)，則稱s和t為等價狀態(tài)。如圖1 中的狀態(tài)6和狀態(tài)7均只能讀出若干b而停于終態(tài)。……