李忠武 保山學(xué)院 云南保山 678000

?

正規(guī)文法與有窮自動機(jī)的等價性研究

李忠武 保山學(xué)院 云南保山 678000

【文章摘要】

正規(guī)表達(dá)式首先由Keene在20世紀(jì)50年代開始研究。McCullough和Pitts提出了一種描述神經(jīng)活動的有窮自動機(jī)模型，從此以后，正規(guī)表達(dá)式和有窮自動機(jī)在計算機(jī)科學(xué)中得到了廣泛應(yīng)用。通常，對于正規(guī)文法G 和有限自動機(jī)M ，M 所定義的語言記作L（G），M 所能識別的語言記作L（M），如果有L（G）=L（M），則稱G 和M是等價的。

【關(guān)鍵詞】

正規(guī)式；正規(guī)文法；構(gòu)造方法；等價性；有限自動機(jī)

引言

正規(guī)表達(dá)式的遞歸定義

（2）如果a是∑上的一個符號，那么a是一個正規(guī)表達(dá)式，并且。也就是說，這個語言僅包含一個長度為1的符號串a(chǎn) 。

（3）假定U和V都是∑上的正規(guī)表達(dá)式，分別表示語言為L（U）和L（V），那么，U |V、 U·V和（U）*也都是正規(guī)式，它們所表示的正規(guī)集分別為L（U）∪L（V）、L（U）L（V）（連接積）和（（閉包）

僅由有限次使用上述三步驟而定義的表達(dá)式才是∑上的正規(guī)式。

有窮自動機(jī)的定義

有限自動機(jī)是識別器，只能對每個可能的輸入串簡單回答“是”或“否”。它分為不確定的有窮自動機(jī)和確定的有窮自動機(jī)。

正規(guī)文法的概念

文法G 可定義為四元組，其中VN為非終結(jié)符的集合，VT為終結(jié)符的集合，P 為產(chǎn)生式的集合，S 為開始符號。若P 中的每個產(chǎn)生式的形式都是或A→a，其中A、B都是非終結(jié)符，a∈VT*，則G 是正規(guī)文法。

1　正規(guī)文法與有限自動機(jī)的等價性

對于正規(guī)文法G 和有限自動機(jī)M ，如果L（G）=L（M）f，則稱G和M是等價的。

關(guān)于它們兩者的等價性，有以下結(jié)論：

1.對于每一個右線性正規(guī)文法G或左線性正規(guī)文法G ，都存在一個有限自動機(jī)，使得L（M）=L（R）。

證明1：

則令。與（1）類似。可以證明。

證明2：

因而，在M中有一條從S0出發(fā)依次經(jīng)過A1，...，AK-1到達(dá)終態(tài)的通路，該通路上所有箭弧的標(biāo)記依次為a1，...ak。反之亦然。所以，當(dāng)且僅當(dāng)。

現(xiàn)在考慮S0F的情形

所以，在上述GR中添加新的非終結(jié)符號t'，t'S和產(chǎn)生式，并用t'代替t作開始符號。這樣修正GR后得到的文法GR'仍是右線性正規(guī)文法，并且。

（2）類似于（1），從NFA M出發(fā)可構(gòu)造左線性正規(guī)文法GL，使得。

最后，由DFA和NFA之間的等價性，結(jié)論2得證。

2　等價性應(yīng)用舉例

圖1　狀態(tài)轉(zhuǎn)換圖

（a）初始的轉(zhuǎn)換圖；（b）從等價的右線性正規(guī)文化導(dǎo)出的轉(zhuǎn)換圖

GR=＜｛0，1｝，｛A，B，C，D｝，A，P＞，其中P由下列產(chǎn)生式組成：

NFA M出發(fā)構(gòu)造左線性正規(guī)文法GL=＜｛0，1｝，｛B，C，D，f｝，f，P＞，其中P由下列產(chǎn)生式組成：

易證L（GL）=L（M）。

3　結(jié)束語

有限自動機(jī)狀態(tài)轉(zhuǎn)換圖的形式化表示。它指是一個開始狀態(tài)、一個或多個接受狀態(tài)，以及狀態(tài)集、輸入字符和狀態(tài)間的轉(zhuǎn)換集合。接受狀態(tài)表明已經(jīng)發(fā)現(xiàn)了和某個詞法單元對應(yīng)的詞素。有限自動機(jī)即可以在輸入字符上執(zhí)行轉(zhuǎn)換，也可以在空輸入上執(zhí)行轉(zhuǎn)換。

正規(guī)式是正規(guī)文法、有窮自動機(jī)FA的代數(shù)化表示，它的表示準(zhǔn)確、緊湊、高效，可以構(gòu)造高效的詞法分析器.用于詞法分析器的自動生成，也用于各種信息（如模式識別、情報檢索。

狀態(tài)轉(zhuǎn)換圖是正規(guī)文法、有窮自動機(jī)FA的圖形表示，直觀易懂，與通常的程序流程圖很相近，易于實現(xiàn)程序的編制。

【參考文獻(xiàn)】

［1］陳火旺，劉春林，譚慶平，趙克佳，劉越.程序設(shè)計語言編譯原理［M］. 北京：國防工業(yè)出版社，2013： P53.

［2］葛寒松.正規(guī)文法與有限自動機(jī)的等價性研究［J］. 河南：商丘師范學(xué)院學(xué)報，2010，26（12）：P75.

［3］胡元義.編譯原理教程（第2版）［Z］. 西安：西安電子科技大學(xué)出版社， 2006.