形式語言與自動機-5-dfa與nfa等價性及正則運算封閉性-預覽頁
【正文】 {1},{1, 2}UJS* 15n 重新排列：重新排列：UJS* 16第五章第五章 DFA與與 NFA等價性等價性及正則運算封閉性及正則運算封閉性n NFA 與與 DFA的等價性的等價性n 正則語言類在正則運算下的封閉性正則語言類在正則運算下的封閉性– – 連接運算下的封閉性連接運算下的封閉性– 星號運算下的封閉性星號運算下的封閉性UJS* 17n 前面已經說過，正則語言在正則運算下前面已經說過，正則語言在正則運算下是封閉的。我們僅完成了并運算的證明，而放棄了連接運算成了并運算的證明，而放棄了連接運算封閉性的證明，因為太復雜。UJS* 18第五章第五章 DFA與與 NFA等價性等價性及正則運算封閉性及正則運算封閉性n NFA 與與 DFA的等價性的等價性n 正則語言類在正則運算下的封閉性正則語言類在正則運算下的封閉性– – 連接運算下的封閉性連接運算下的封閉性– 星號運算下的封閉性星號運算下的封閉性UJS* 19n 定理定理 1：正則語言類在并運算下封閉。想法是對 A1和和A2取兩臺取兩臺 NFA，記為，記為 N1和和 N2，把他們合，把他們合并為一臺新的并為一臺新的 NFA，記為，記為 N。機器的起始狀態(tài)。下圖給出了這個構造。構造識別。UJS* 23第五章第五章 DFA與與 NFA等價性等價性及正則運算封閉性及正則運算封閉性n NFA 與與 DFA的等價性的等價性n 正則語言類在正則運算下的封閉性正則語言類在正則運算下的封閉性– – 連接運算下的封閉性連接運算下的封閉性– 星號運算下的封閉性星號運算下的封閉性UJS* 24n 定理定理 2：正則語言類在連結運算下封閉。想法是對 A1和和 A2取兩臺取兩臺 NFA，記為，記為 N1和和 N2，把他們合并，把他們合并為一臺新的為一臺新的 NFA，記為，記為 N。起始狀態(tài)。– (1) Q = Q1∪∪ Q2– (2) q1是是 N的起始狀態(tài)的起始狀態(tài)– (3) F = F2UJS* 27n (4) 定義定義 δ如下：對于每一個如下：對于每一個 q∈∈ Q每一個每一個a∈∈ ∑ε, 下式成立：下式成立：UJS* 28第五章第五章 DFA與與 NFA等價性等價性及正則運算封閉性及正則運算封閉性n NFA 與與 DFA的等價性的等價性n 正則語言類在正則運算下的封閉性正則語言類在正則運算下的封閉性– – 連接運算下的封閉性連接運算下的封閉性– 星號運算下的封閉性星號運算下的封閉性UJS* 29n 定理定理 3：正則語言類在星號運算下封閉。想法是對 A1取臺取臺 NFA，記為，記為 N1，構造一，構造一臺新的臺新的 NFA，記為，記為 N，能識別，能識別 A1*
數(shù)學相關推薦
鄂ICP備17016276號-1