簡(jiǎn)介

本節(jié)主要是介紹計(jì)算理論上的一些基本概念, 和一個(gè)最簡(jiǎn)單的計(jì)算模型, 即自動(dòng)機(jī)模型. 自動(dòng)機(jī)模型能解決的問(wèn)題相當(dāng)有限, 但是是圖靈機(jī)模型的基礎(chǔ)并且它足夠簡(jiǎn)單, 因此以它作為一個(gè)入門是一個(gè)相當(dāng)好的選擇. 如果有學(xué)習(xí)過(guò)<算法導(dǎo)論>中的字符串匹配部分, 那么對(duì)這個(gè)概念應(yīng)該并不陌生.
自動(dòng)機(jī)模型和圖靈機(jī)模型之間, 是下推自動(dòng)機(jī)模型, 其功能強(qiáng)于自動(dòng)機(jī), 但弱于圖靈機(jī), 主要是程序語(yǔ)言理論中研究的核心模型, 我們暫且不研究程序語(yǔ)言理論, 因此也不介紹下推自動(dòng)機(jī).

計(jì)算問(wèn)題

什么是計(jì)算機(jī)?

計(jì)算, 就是解決某個(gè)具體問(wèn)題的算法, 得出相應(yīng)的答案. 計(jì)算機(jī)就是能執(zhí)行某個(gè)具體算法的機(jī)器. 即Computer就用來(lái)是Compute的機(jī)器. 此外, 討論什么是機(jī)器, 對(duì)我們研究計(jì)算機(jī)科學(xué)毫無(wú)幫助, 你只需要知道, 計(jì)算機(jī)就是用來(lái)執(zhí)行算法的機(jī)器. 我們要做的就是, 用最簡(jiǎn)單的理論模型, 最大程度的抽象化我們現(xiàn)有的計(jì)算機(jī).

語(yǔ)言

定義語(yǔ)言

一個(gè)字母表(alphabet)是一個(gè)非空有限集合, 該集合中的元素稱為符號(hào)(symbol).

一個(gè)字母表 $\Sigma$ 上的語(yǔ)言(language)是 $\Sigma$ 中的元素構(gòu)成的有限序列(稱為串, 即string)的集合.

例如字母表 $\Sigma=\{0,1\}$ , 則我們可以定義一個(gè) $\Sigma$ 上的語(yǔ)言 $L=\{x_1x_2\cdots x_n|\text{如果}x_i= 0,則x_{i+1}= 0\}$ , 則該語(yǔ)言為
$L=\{\varepsilon, 0,1,10,11,100,110,111,\cdots\}$
即所有的 $1$ 都出現(xiàn)在任何 $0$ 之前的串. 其中, $\varepsilon$ 表示空串, 即長(zhǎng)度為 $0$ 的串.

這里要注意的是

我們說(shuō)"序列"就要考慮順序, 即 $001?$ 和 $100?$ 是不同的串.
串可以是空串, 即長(zhǎng)度為 $0$ 的串, 空串通常記作 $\varepsilon$ .

我們也可用更加形式化的描述來(lái)定義語(yǔ)言.

定義語(yǔ)言

設(shè) $\Sigma?$ 是一個(gè)字母表, $\Sigma^0=\{\varepsilon\}?$ 表示空串的集合, $\Sigma^n=\Sigma\times \Sigma\times\cdots\times \Sigma?$ 為 $n?$ 個(gè) $\Sigma?$ 的直積. 則 $\Sigma?$ 上的一個(gè)語(yǔ)言定義為 $\Sigma^\ast=\bigcup\limits_{i\in\mathbb{N}}\Sigma^i?$ 的子集.

這里要注意的是 $\Sigma^0$ 不是空集, 而是含有一個(gè)特殊的元素 $\varepsilon$ .

語(yǔ)言這個(gè)詞可以說(shuō)是一個(gè)相當(dāng)糟糕的術(shù)語(yǔ), 我們?cè)谶@里不對(duì)這個(gè)術(shù)語(yǔ)本身進(jìn)行過(guò)多的討論, 但我們舉例說(shuō)明語(yǔ)言有多強(qiáng)大. 我們舉一個(gè)有意義的例子.

例如, 一個(gè)語(yǔ)言可以用來(lái)表示所有的有向無(wú)環(huán)圖, 我們?cè)噲D用字母表 $\Sigma=\{0,1\}$ 上的語(yǔ)言來(lái)對(duì)圖進(jìn)行編碼. 首先我們需要表示圖 $G=(V,E)$ 中的 $V$ , 我們約定 $\dagger$ 之前的部分表示圖中每個(gè)點(diǎn)的名稱的長(zhǎng)度 $v$ , 而 $\dagger$ 之后依次的每個(gè)長(zhǎng)度為 $v$ 的連續(xù)子串表示圖所有點(diǎn)的名稱. 在所有的名稱后, 我們用另一個(gè) $\dagger$ 作為分割, 其后依次的每個(gè)長(zhǎng)度為 $2v$ 子串表示一條有向邊. 所有的有向邊后以 $\ddagger?$ 結(jié)束.

例如圖

可以被表示為

$100\dagger0010\cdot0011\cdot0101\cdot0111\cdot1000\cdot1001\cdot1010\cdot1010\cdot1011\dagger\\0011\to1000\cdot0011\to1010\cdot0011\to1010\cdot0101\to1011\cdot\\0111\to1000\cdot0111\to1011\cdot 1000\to1001\cdot1011\to0010\cdot\\10011\to1010\ddagger$

在上述編碼中, 作如下替換
$0\to01,1\to10,\dagger\to00,\ddagger\to11,\cdot\to\varepsilon$
即為該有向圖的在該語(yǔ)言中的編碼. 所有的有向無(wú)環(huán)圖構(gòu)成的語(yǔ)言, 即所有的有向無(wú)環(huán)圖按照上述編碼構(gòu)成的語(yǔ)言. 值得一提的是, 上述語(yǔ)言對(duì)有向圖的編碼并不是雙射, 但是我們可以增適當(dāng)?shù)南拗剖沟迷撜Z(yǔ)言對(duì)有向圖的編碼成為雙射.

按照類似的方式, 我們可以用語(yǔ)言表示, 所有的合取范式\無(wú)環(huán)布爾電路\樹(shù)等. 大多數(shù)情況下, 我們不討論具體的編碼方式, 而是直接討論語(yǔ)言, 如"所有的合取范式構(gòu)成的語(yǔ)言".

判定問(wèn)題

計(jì)算理論中最簡(jiǎn)單的問(wèn)題, 就是判定問(wèn)題, 即只能用 $\text{YES},\text{NO}$ 回答的問(wèn)題. 這類問(wèn)題非常普遍, 例如問(wèn)某個(gè)有向圖是不是有向無(wú)環(huán)圖, 那么這個(gè)問(wèn)題的算法, 實(shí)際上是建立了一個(gè)映射. 如果用 $L_{G}$ 表示所有的有向圖構(gòu)成的語(yǔ)言, 并用 $0,1$ 分別表示 $\text{YES},\text{NO}$ , 那么這個(gè)問(wèn)題實(shí)際上就是建立了一個(gè)映射 $f:\{0,1\}^\ast\to \{0,1\}$ , 且 $f(x)=1$ 當(dāng)且僅當(dāng) $x\in L_G$ . 而解決這個(gè)問(wèn)題算法就是能夠計(jì)算函數(shù) $f?$ 的算法.

不難得出, 每一個(gè)語(yǔ)言都對(duì)應(yīng)一個(gè)判定問(wèn)題, 因此我們不再區(qū)分語(yǔ)言和判定問(wèn)題, 我們可以直接說(shuō)判定問(wèn)題 $L_G$ , 即判定一個(gè)有向圖是否為有向無(wú)環(huán)圖的問(wèn)題. 此后的絕大多數(shù)情況, 我們關(guān)心的問(wèn)題都是判定問(wèn)題.

有的讀者會(huì)問(wèn), 為什么我們要如此關(guān)注判定問(wèn)題? 因?yàn)樵谖唇佑|到這方面理論的人的直觀思維中, 判定問(wèn)題是一類非常弱的問(wèn)題, 弱到連自然數(shù)的加法都無(wú)法計(jì)算. 確實(shí)如此, 但是判定問(wèn)題和非判定問(wèn)題之間存在天然的關(guān)系, 每一個(gè)非判定問(wèn)題都可以轉(zhuǎn)換為判定問(wèn)題. 例如, 計(jì)算問(wèn)題 $f:(x,y)\mapsto x+y$ 可以轉(zhuǎn)換為判定問(wèn)題 $g:\{(x,y,z)|x,y,z\in\mathbb{Z}_+\}\to\{0,1\}$ , 其中 $g(x,y,z)=1$ 當(dāng)且僅當(dāng) $x+y=z$ , 即判定 $z$ 是否為 $x$ 和 $y$ 的和的問(wèn)題. 而且兩者的復(fù)雜度之間存在深刻的關(guān)系, 我們將在之后的章節(jié)中具體介紹.

自動(dòng)機(jī)模型

有限狀態(tài)機(jī)

定義有限狀態(tài)機(jī) (finite state machine)
一個(gè)有限狀態(tài)機(jī)是一個(gè)五元組 $(Q,\Sigma,\delta,q_0,F)$ , 其中

$Q$ 是一個(gè)有限集, 稱為狀態(tài)集

$\Sigma?$ 是一個(gè)有限集, 稱為字母表

$\delta:Q\times\Sigma \to Q$ 稱為轉(zhuǎn)移函數(shù)

$q_0\in Q$ 是起始狀態(tài)

$F\subseteq Q?$ 是接受狀態(tài)集

有限狀態(tài)機(jī)也被稱為自動(dòng)機(jī)(automaton)，自動(dòng)機(jī)不是什么復(fù)雜的東西, 一個(gè)自動(dòng)機(jī)可以用一張類似于這樣的圖表示:

其中:

圓圈表示狀態(tài)
- 有一條沒(méi)有起點(diǎn)的箭頭指向的狀態(tài)為起始狀態(tài)
- 雙圈表示的狀態(tài)是接受狀態(tài)
帶符號(hào)集的箭頭表示轉(zhuǎn)移函數(shù)中的一組映射

例如 $q_2\overset{0,1}{\longrightarrow}q_3?$ 表示映射 $(q_2,0)\mapsto q_3?$ 和 $(q_2,1)\mapsto q_3?$ 兩條映射

當(dāng)有限狀態(tài)機(jī)處于某個(gè)狀態(tài)的時(shí)候, 讀取到相應(yīng)的符號(hào), 有限狀態(tài)機(jī)會(huì)根據(jù)轉(zhuǎn)移函數(shù)跳轉(zhuǎn)到下一狀態(tài). 例如上圖中, 當(dāng)有限狀態(tài)機(jī)處于 $q_1$ 狀態(tài)時(shí), 如果讀到的下一符號(hào)為 $0$ , 根據(jù)轉(zhuǎn)移函數(shù) $(q_1,0)\mapsto q_1$ , 則在讀取該符號(hào)后, 有限狀態(tài)集仍會(huì)處于 $q_1$ 狀態(tài)

注意:

有限狀態(tài)機(jī)(finite state machine)也可以稱為自動(dòng)機(jī)(automaton), 但不能稱為"有限自動(dòng)機(jī)".
我們說(shuō)"自動(dòng)機(jī)"就是指"有限狀態(tài)機(jī)", 而不是“自動(dòng)機(jī)”"下推自動(dòng)機(jī)""非確定自動(dòng)機(jī)"等一系列計(jì)算模型的統(tǒng)稱.

復(fù)雜度類REG

現(xiàn)在我們要討論一類相當(dāng)簡(jiǎn)單的語(yǔ)言, 和由它們構(gòu)成的復(fù)雜度類REG.

從上面有關(guān)于自動(dòng)機(jī)的描述, 我們可以看到, 當(dāng)自動(dòng)機(jī) $M=(Q,\Sigma,\delta,q_0,F)$ 處于起始狀態(tài) $q_0$ 時(shí), 我們輸入一個(gè) $\Sigma$ 上的串 $x\in\Sigma^\ast$ , $M$ 會(huì)依次讀取串 $x$ 上的符號(hào), 并根據(jù)狀態(tài)機(jī)作相應(yīng)的狀態(tài)轉(zhuǎn)換. 當(dāng)整個(gè)串 $x$ 讀取完畢后, $M$ 可能處于某個(gè)接受狀態(tài) $q\in F$ , 也可能處于某個(gè)非接受狀態(tài) $q^\prime\notin F$ . 如果一個(gè)串 $x\in \Sigma^\ast$ 使 $M$ 按照上述運(yùn)行方式運(yùn)行后, 處于某個(gè)接受狀態(tài), 就記 $M(x)=1$ 并稱 $M$ 接受串 $x$ , 否則記 $M(x)0=$ 并稱 $M$ 拒絕串 $x$ .

這里要注意拒絕狀態(tài)有兩種情況. 一種是在輸入結(jié)束后, 自動(dòng)機(jī)確實(shí)處于某個(gè)非接受狀態(tài). 另一種是, 在輸入的過(guò)程中, 某一部計(jì)算根據(jù)狀態(tài)和輸入符號(hào), 轉(zhuǎn)移函數(shù)中并沒(méi)有一條映射指出這種情況下機(jī)器應(yīng)該轉(zhuǎn)移到哪個(gè)狀態(tài). 即, 計(jì)算提前結(jié)束了.

根據(jù)這一點(diǎn), 我們可以發(fā)現(xiàn), 自動(dòng)機(jī) $M$ 根據(jù)上述運(yùn)行的方式, 可以表示一個(gè)映射 $f: \Sigma^\ast\to\{0,1\}$ 滿足 $f(x)=1$ 當(dāng)且僅當(dāng) $M(x)=1$ . 如果一個(gè)語(yǔ)言 $L$ 和一個(gè)自動(dòng)機(jī) $M$ 滿足 $x\in L$ 當(dāng)且僅當(dāng) $M(x)=1$ 我們就說(shuō) $M$ 識(shí)別(recognize) $L$ 或判定(decide). 為了統(tǒng)一我們有關(guān)判定的問(wèn)題的敘述, 我們總是使用"判定".

注意: 自動(dòng)機(jī)是按照輸入和轉(zhuǎn)移函數(shù)按部就班地執(zhí)行, 輸入串中每一個(gè)符號(hào)都會(huì)讓自動(dòng)機(jī)執(zhí)行一步, 且只會(huì)執(zhí)行一步, 因此自動(dòng)機(jī)總是在輸入結(jié)束的時(shí)候停機(jī), 因此不會(huì)出現(xiàn)不停機(jī)的情況. 在這樣的限制下識(shí)別和判定是等價(jià)的, 但是對(duì)于其他的計(jì)算模型來(lái)說(shuō), 這兩個(gè)概念并不等價(jià).

現(xiàn)在我們定義一類判定問(wèn)題(不要忘了一個(gè)語(yǔ)言對(duì)應(yīng)一個(gè)判定問(wèn)題, 判定問(wèn)題的集合就是語(yǔ)言的集合)
$\textsf{REG}=\{L|\exists\text{自動(dòng)機(jī)}M: x\in L\iff M(x)\}$
即REG表示那些能夠被一臺(tái)自動(dòng)機(jī)識(shí)別的語(yǔ)言.

例: $L=\{所有包含"001"串\}\in \textsf{REG}$

我們可以構(gòu)造一臺(tái)識(shí)別它的自動(dòng)機(jī)來(lái)說(shuō)明這一點(diǎn)

自動(dòng)機(jī)作為計(jì)算機(jī)

自動(dòng)機(jī)可以被視為一臺(tái)計(jì)算機(jī), 但是是一臺(tái)功能相當(dāng)弱的計(jì)算機(jī). 抽象能力比較強(qiáng)的讀者可以發(fā)現(xiàn), 自動(dòng)機(jī)沒(méi)有任何類似于內(nèi)存的結(jié)構(gòu), 所有需要存儲(chǔ)中間值的才能完成的判定問(wèn)題都不能被自動(dòng)機(jī)完成. 我們稱一個(gè)計(jì)算模型能夠解決問(wèn)題的能力稱為計(jì)算能力, 如果考慮的是判定問(wèn)題, 那么它表示的就該模型能夠判定的語(yǔ)言的集合的一些特征(如和其他模型能夠判定的語(yǔ)言的).

正則語(yǔ)言與自動(dòng)機(jī)

正則語(yǔ)言

現(xiàn)在我們語(yǔ)言的三種運(yùn)算方式, 它們的運(yùn)算結(jié)果仍是一個(gè)語(yǔ)言. 設(shè) $L_1$ 與 $L_2$ 均為語(yǔ)言, 定義它們之間的三種運(yùn)算:
$L_1\circ L_2 = \{x_1x_2|x_1\in L_1, x_2\in L_2\}$
即 $L_1\circ L_2?$ 是所有 $L_1?$ 中的串與 $L_2?$ 中的串拼接構(gòu)成的串的集合, 在不產(chǎn)生歧義的時(shí)候, 這個(gè)圈可以不寫. 根據(jù)concatenation的翻譯, 我們可以稱該運(yùn)算為"串聯(lián)".
$L_1\cup L_2 = \{x|x\in L_1 或 x\in L_2\}$
它所表示的意義和集合的并集一樣.

而 $L_1^\ast?$ 表示的是由 $L_1?$ 中的任意串重復(fù)任意次(如果重復(fù) $0?$ 次就得到 $\varepsilon?$ )所得到的所有的串構(gòu)成的集合. 例如 $L_1=\{00, 01\}?$ , 那么 $\varepsilon,00,01,0000,0101,000000,010101?$ 等都是 $L_1^\ast?$ 的元素. 如果讀者更傾向于形式化的定義, 那么 $L_1^\ast?$ 可以定義為

$L^0=\{\varepsilon\}, \quad L^n=\{x^n|x\in L\} \\ L^\ast= \bigcup_{i\in\mathbb{N}} L^i$
這三種運(yùn)算稱為正則運(yùn)算, 我們不過(guò)度糾結(jié)運(yùn)算的優(yōu)先級(jí)問(wèn)題, 并總是在需要的時(shí)候用括號(hào)表示運(yùn)算的順序.

現(xiàn)在我們來(lái)定義正則語(yǔ)言(regular language), 它包括一類最基本的語(yǔ)言, 和這類最基本的語(yǔ)言按照上述三種方式做運(yùn)算產(chǎn)生的語(yǔ)言.

定義正則語(yǔ)言

一個(gè)語(yǔ)言 $L?$ 是正則語(yǔ)言, 如果它滿足以下命題之一

$L=\{a\}?$ , 其中 $a?$ 是某個(gè)字母表 $\Sigma?$ 上的符號(hào);

$L=\{\varepsilon\}$ ;

$L=\emptyset$ ;

$L=L_1\cup L_2$ , 其中 $L_1$ 和 $L_2$ 均為正則語(yǔ)言;

$L=L_1\circ L_2$ , 其中 $L_1$ 和 $L_2$ 均為正則語(yǔ)言;

$L=L_1^\ast$ , 其中 $L_1$ 為正則語(yǔ)言;

要注意的是, 4.5.6.表示的運(yùn)算中, 空集也可以參與, 并且有:

空集與任何語(yǔ)言作 $\circ$ 或 $\cup$ 運(yùn)算得到的都是空集
$\emptyset^\ast=\{\varepsilon\}$

這兩點(diǎn)實(shí)際上也可以通過(guò)這些運(yùn)算的定義得出.

如果是初次接觸正則語(yǔ)言可能會(huì)覺(jué)得有些奇怪, 但是我們?cè)趯W(xué)習(xí)正則表達(dá)式并了解自動(dòng)機(jī)與正則語(yǔ)言的關(guān)系后, 這個(gè)概念會(huì)變得更加清晰.

從正則語(yǔ)言的定義種可以得到, 一個(gè)僅包含有限個(gè)串的語(yǔ)言總是一個(gè)正則語(yǔ)言, 因?yàn)樗梢詫懗伤乃袉蝹€(gè)串構(gòu)成的語(yǔ)言的 $\cup$ . 而每個(gè)單個(gè)串構(gòu)成的語(yǔ)言又可以看作是僅有一個(gè)長(zhǎng)度為1的串構(gòu)成的語(yǔ)言的并聯(lián).

正則表達(dá)式

注意! 我們這里介紹的并不是用于在Linux系統(tǒng)中查詢的正則表達(dá)式, 盡管我們介紹的正則表達(dá)式和它的功能一致. 但我們也會(huì)對(duì)Linux系統(tǒng)中的正則表達(dá)式某些符號(hào)的具體意思做出解釋.

正則表達(dá)式(regular expression)是用來(lái)描述一個(gè)正則語(yǔ)言的, 它由字母表種的符號(hào), $\cup$ 運(yùn)算符, $\circ$ 運(yùn)算符, $^\ast$ 運(yùn)算符還有括號(hào)組成. 我們可以用這些符號(hào)連同括號(hào)的組合來(lái)表示一個(gè)正則語(yǔ)言, 同樣的, 這里的 $\circ$ 在不產(chǎn)生歧義的情況下也可以略去不寫.

例如, 正則表達(dá)式 $R = (0\circ(0\cup 1))^\ast$ , 表示語(yǔ)言
$L=\{\varepsilon, 00, 01, 0000, 0100, 0101, \cdots\}$
即所有長(zhǎng)度為偶數(shù)且 $1$ 只出現(xiàn)在從左至右第偶數(shù)位的串. 它的原理很簡(jiǎn)單, 它由長(zhǎng)度為2單元 $0\circ (0\cup 1)$ 重復(fù)任意次組成, 而在一以個(gè)單元種, 第一位必須是0, 第二位可以是1或0. 實(shí)際上這個(gè)語(yǔ)言確實(shí)是正則語(yǔ)言, 令 $L_0=\{0\}, L_1=\{1\}$ , 那么有
$L= (L_0\circ (L_0\cup L_1))^\ast$
顯然復(fù)合正則語(yǔ)言的定義.

我們現(xiàn)在來(lái)定義正則表達(dá)式, 并用一些例子在說(shuō)明它是如何運(yùn)作的.

定義正則表達(dá)式

一個(gè)表達(dá)式 $R?$ 為正則表達(dá)式, 如果它是以下幾種表達(dá)式之一

$a$ , 其中 $a$ 是字母表 $\Sigma?$ 中的一個(gè)元素;

$\varepsilon?$ ;

$\emptyset$ ;

$(R_1\cup R_2)$ , 其中 $R_1$ 和 $R_2$ 是正則表達(dá)式

$(R_1\circ R_2)$ , 其中 $R_1$ 和 $R_2$ 是正則表達(dá)式

$(R_1^\ast)$ , 其中 $R_1$ 是正則表達(dá)式

同時(shí)這里也要注意和空集的運(yùn)算, 與正則語(yǔ)言類似, 這里不再贅述.

可以看出, 正則語(yǔ)言和正則表達(dá)式非常相似. 注意有時(shí)候, 我們會(huì)簡(jiǎn)化正則表達(dá)式的寫法, 讓整個(gè)串充當(dāng)一個(gè)字母的角色, 并且可以用或( $|$ )連接一些串, 同時(shí)出現(xiàn)可選串 $[]$ . 例如
$R= (10 | 01) [00] 1$
表示語(yǔ)言
$L={101,011,10001,01001}$
它的原理也非常簡(jiǎn)單, 每個(gè)串都是一些僅有字母表中一個(gè)符號(hào)構(gòu)成的語(yǔ)言的串聯(lián), 而或( $|$ )表示的就是 $\cup$ , 而 $[x]$ 表示的是 $x|\varepsilon$ . 用這種方式表達(dá)的正則表達(dá)式, 就是我們常用于查詢的正則表達(dá)式.

而如果或( $|$ )連接的是一些長(zhǎng)度為1的串, 我們也更習(xí)慣將它表示為這些串的符號(hào)的集合, 例如 $(a|b|c)^\ast$ 可以表示為 $\{a,b,c\}^\ast$ , 如果這個(gè)集合就是字母表 $\Sigma$ , 我們還可以寫作 $\Sigma^\ast$ . 同時(shí), 如果我們希望重復(fù)一個(gè)串 $x$ 大于等于 $1$ 次也可以用 $x^+$ 來(lái)表示, 即 $x^+=x \circ (x^\ast)$ .

例子設(shè) $\Sigma=\{0,1\}$

$0^\ast 10^\ast=\{w|w恰好有一個(gè)1\}$
$(\Sigma\Sigma\Sigma)^\ast=\{w|w的長(zhǎng)度正好是3的倍數(shù)\}?$
$2333(3^\ast)=\{w|w是由2333開(kāi)頭且在之后是任意長(zhǎng)度的純3串\}$

其中3.中表示的正則表達(dá)式有助于屏蔽彈幕中那些過(guò)長(zhǎng)的類 $233$ 串, 例如 $2333333333333333333333$ .

注意: 我們始終沒(méi)有證明正則語(yǔ)言和正則表達(dá)式的對(duì)等性, 即一個(gè)正則表達(dá)式表示一個(gè)正則語(yǔ)言, 一個(gè)正則語(yǔ)言總可以用一個(gè)正則表達(dá)式表示. 我們不打算證明這一點(diǎn), 因?yàn)槲覀冋J(rèn)為讀者的直覺(jué)能夠察覺(jué)這一點(diǎn), 如果喜歡學(xué)習(xí)嚴(yán)格的證明, 還是請(qǐng)閱讀教材或論文.

定理1

一個(gè)語(yǔ)言 $L$ 是正則語(yǔ)言, 當(dāng)且僅當(dāng)它能夠被表示成某個(gè)正則表達(dá)式 $R$ .

非確定自動(dòng)機(jī)

非確定性

非確定性(nondeterminism)是不是非確定自動(dòng)機(jī)獨(dú)有的, 我們還會(huì)在其他的計(jì)算模型中遇到非確定性, 因此我們決定先介紹非確定性, 再介紹非確定自動(dòng)機(jī).

在自動(dòng)機(jī)模型中, 一個(gè)自動(dòng)機(jī)在接受相同的輸入時(shí), 總是執(zhí)行相同的計(jì)算步驟, 并總是得到相同的結(jié)果, 這樣的計(jì)算方式稱為確定的(deterministic). 即, 計(jì)算步驟與時(shí)間無(wú)關(guān)(如果我們將從宇宙大爆炸到目前為止的時(shí)間視作一個(gè)隱藏的參數(shù)的話/如果讀者知道實(shí)時(shí)系統(tǒng)的定義, 那么對(duì)這個(gè)描述應(yīng)該不會(huì)感到突兀). 這可能有點(diǎn)決定論的味道, 但也是一種理解方式. 反之, 非確定性, 就是, 一次具體的計(jì)算過(guò)程, 與時(shí)間有關(guān). 或者, 我們可以更加直觀地說(shuō), 一臺(tái)具有非確定性的計(jì)算機(jī), 在接受相同輸入時(shí), 計(jì)算步驟和結(jié)果可能有所不同.

非確定自動(dòng)機(jī)

自動(dòng)機(jī)具有確定性是因?yàn)樽詣?dòng)機(jī)處在任意狀態(tài)時(shí), 對(duì)于某個(gè)具體的輸入, 根據(jù)轉(zhuǎn)移函數(shù), 改機(jī)器僅能轉(zhuǎn)移到至多一個(gè)狀態(tài), 即轉(zhuǎn)移的結(jié)果是唯一的. 如果我們修改這一條定義, 將轉(zhuǎn)移的方式改為不確定的, 那么我們就得到非確定自動(dòng)機(jī)(nondeterministic automaton).

為了避免讀者對(duì)于陌生數(shù)學(xué)符號(hào)的恐懼, 我們解釋一下超集. 有限集的超集非常容易理解, 一個(gè)有限集 $S$ 的超集, 是它的所有子集的集合, 記作 $\mathcal{P}(S)$ . 例如 $S=\{a,b,c\}$ , 那么它一共有8個(gè)子集
$\emptyset,\{a\},\{b\},\{c\},\{ab\},\{ac\},\{bc\},\{abc\}$
其超集就是以上8個(gè)集合組成的集族(一般我們稱集合的集合為集族, 也可簡(jiǎn)稱為族).

定義非確定自動(dòng)機(jī)

一個(gè)非確定自動(dòng)機(jī)是一個(gè)五元組 $(Q,\Sigma_{\varepsilon},\delta,q_0,F)$ , 其中

$Q$ 是一個(gè)有限集, 稱為狀態(tài)集

$\Sigma_{\varepsilon}$ 是一個(gè)有限集, 是字母表和空串 $\varepsilon$ 的并集.

$\delta:Q\times\Sigma_\varepsilon \to \mathcal{P}(Q)?$ 稱為轉(zhuǎn)移函數(shù)

$q_0\in Q$ 是起始狀態(tài)

$F\subseteq Q?$ 是接受狀態(tài)集

這里與自動(dòng)機(jī)相比, 唯一不同的一點(diǎn)在于轉(zhuǎn)移函數(shù), 非確定自動(dòng)機(jī)的轉(zhuǎn)移函數(shù)的上域(codomain)(注意不是值域!)變?yōu)榱藸顟B(tài)集 $Q$ 的超集 $\mathcal{P}(Q)$ . 除此之外, 非確定自動(dòng)機(jī)的轉(zhuǎn)移函數(shù)還能接受輸入 $\varepsilon$ , 即在不接受任何輸入的時(shí)候也可能隨機(jī)發(fā)生轉(zhuǎn)移. 回想一下, 自動(dòng)機(jī)在處于某個(gè)狀態(tài)時(shí), 接受某個(gè)符號(hào)會(huì)轉(zhuǎn)移到一個(gè)唯一確定的狀態(tài), 而處于某個(gè)狀態(tài)的非確定自動(dòng)機(jī), 接受某個(gè)符號(hào)的輸入, 則會(huì)有一些狀態(tài)構(gòu)成的集合作為"候選"狀態(tài), 非確定自動(dòng)機(jī)會(huì)隨機(jī)地從這些狀態(tài)中選擇一個(gè)進(jìn)行轉(zhuǎn)移.

如果我們將非確定自動(dòng)機(jī)的每一次轉(zhuǎn)移視作它產(chǎn)生了幾個(gè)并行的計(jì)算分支, 那么我們由如下圖所示的描述

1548543326251.png

其中左圖為自動(dòng)機(jī)的計(jì)算步驟, 其每一步計(jì)算都是僅產(chǎn)生一個(gè)計(jì)算分支, 而整個(gè)計(jì)算過(guò)程由一個(gè)計(jì)算分支過(guò)程, 自動(dòng)機(jī)是否決定某個(gè)串, 取決于這個(gè)唯一的計(jì)算分支是否在串的輸入結(jié)束后處于接受狀態(tài). 類似的, 我們通過(guò)這一點(diǎn)將接受的概念推廣到非確定自動(dòng)機(jī)上.

非確定自動(dòng)機(jī)每一步都會(huì)產(chǎn)生多個(gè)計(jì)算分支, 而整個(gè)計(jì)算過(guò)程的計(jì)算分支可能會(huì)非常復(fù)雜. 非確定自動(dòng)機(jī)的整個(gè)計(jì)算過(guò)程可以用一個(gè)深度和輸入長(zhǎng)度加1相等的樹(shù)來(lái)表示, 其每個(gè)節(jié)點(diǎn)都是一個(gè)非確定自動(dòng)機(jī)的狀態(tài), 而路徑則是合法的轉(zhuǎn)移. 通過(guò)這種方式, 我們可以知道, 每一條根到葉子的路徑都是一條計(jì)算分支. 先在我們定義: 如果非確定自動(dòng)機(jī) $N$ 在輸入 $x$ 時(shí)存在一條計(jì)算分支在輸入結(jié)束后處于接受狀態(tài), 我們就說(shuō)非確定自動(dòng)機(jī) $N$ 接受輸入 $x$ , 記作 $N(x)=1$ . 否則, 我們稱非確定自動(dòng)機(jī) $N$ 拒絕串 $x$ , 記作 $N(x)=0$ .

例如下面的非確定自動(dòng)機(jī), 處在 $q_1$ 狀態(tài)時(shí), 可能會(huì)隨機(jī)轉(zhuǎn)移到 $q_3$ 狀態(tài). 而當(dāng)它處于 $q_2$ 狀態(tài)并收到輸入 $a$ 時(shí), 可能轉(zhuǎn)移到 $q_2$ 或 $q_3$ 狀態(tài). 當(dāng)模擬其計(jì)算過(guò)程時(shí), 可以計(jì)算通過(guò)將每一步機(jī)器可能處于的狀態(tài)視作一個(gè)集合(我們稱為合法狀態(tài)集), 并在收到某個(gè)輸入符號(hào)時(shí), 計(jì)算每個(gè)合法狀態(tài)集中的狀態(tài)對(duì)應(yīng)該符號(hào)根據(jù)轉(zhuǎn)移函數(shù)得到的狀態(tài)集合的并集. 例如下圖中的非確定自動(dòng)機(jī)根據(jù)輸入 $bc$

首先在起始狀態(tài)時(shí), 可能隨機(jī)轉(zhuǎn)移到狀態(tài) $q_3$ , 因此此時(shí)的合法狀態(tài)集是 $\{q_1,q_3\}$
在收到第一個(gè)輸入 $b$ 時(shí), 狀態(tài) $q_1$ 只能轉(zhuǎn)移到 $q_2$ , 而狀態(tài) $q_3$ 根據(jù)輸入 $b$ 無(wú)法轉(zhuǎn)移, 因此這一步的合法狀態(tài)集為 $\{q_2\}$
在收到第二個(gè)輸入 $c$ 時(shí), 狀態(tài) $q_2$ 無(wú)法轉(zhuǎn)移, 因此這一步的合法狀態(tài)集為 $\emptyset$ .

因此該非確定自動(dòng)機(jī)應(yīng)該是拒絕串 $bc$ .

如果熟悉并行計(jì)算, 那么非確定自動(dòng)機(jī)的計(jì)算步驟可以理解為"并行的", 即每一條計(jì)算分支相當(dāng)于被非確定自動(dòng)機(jī)并行的執(zhí)行了. 需要注意的是, 計(jì)算分支數(shù)很可能是無(wú)限多的, 這樣的機(jī)器在現(xiàn)實(shí)世界中也太可能被制造出, 但可以通過(guò)算法模擬.

非確定自動(dòng)機(jī)的計(jì)算能力

從自動(dòng)機(jī)與非確定自動(dòng)機(jī)的定義可以看出, 自動(dòng)機(jī)是非確定自動(dòng)機(jī)中很特殊的一類機(jī)器, 相當(dāng)于是機(jī)器處于任意狀態(tài)時(shí), 收到任意輸入符號(hào), 僅能轉(zhuǎn)移到至多一個(gè)狀態(tài)的非確定自動(dòng)機(jī).

現(xiàn)在我們通過(guò)建立一臺(tái)指定任意非確定自動(dòng)機(jī) $N$ 計(jì)算能力相同的自動(dòng)機(jī) $M$ , 來(lái)說(shuō)明, 自動(dòng)機(jī)和非確定自動(dòng)的計(jì)算能力是相同的. 即

定理2

設(shè) $L$ 為語(yǔ)言. 存在一臺(tái)自動(dòng)機(jī) $M$ 判定 $L$ , 當(dāng)且僅當(dāng)存在一臺(tái)非確定自動(dòng)機(jī) $N$ 判定 $L$ .

回想一下我們"合法狀態(tài)集", 非確定自動(dòng)機(jī) $N$ 處在某一步計(jì)算時(shí), 在接受另一個(gè)輸入, 可以視作從一個(gè)合法狀態(tài)集轉(zhuǎn)移到了一個(gè)另一個(gè)合法狀態(tài)集, 而一個(gè)輸入是否被接受, 取決于非確定自動(dòng)機(jī)在該輸入下最后一步計(jì)算對(duì)應(yīng)的合法狀態(tài)集中是否有接受狀態(tài), 因此我們通過(guò)這一點(diǎn), 將一臺(tái)非確定自動(dòng)機(jī) $N(Q, \Sigma_\varepsilon,\delta, q_0,F)$ , 變?yōu)橐慌_(tái)自動(dòng)機(jī) $M$ .

由于每一步計(jì)算都視為合法狀態(tài)集到合法狀態(tài)集的轉(zhuǎn)換, 因此, $M$ 中的狀態(tài)集應(yīng)該是 $Q$ 的超集, 即 $\mathcal{P}(Q)$ .
由于自動(dòng)機(jī)不能發(fā)生隨機(jī)轉(zhuǎn)移, 因此, $\varepsilon$ 不能參與轉(zhuǎn)移, 即自動(dòng)機(jī)的第二個(gè)參數(shù)退化為 $\Sigma$ .
轉(zhuǎn)移函數(shù) $\delta^\prime$ 肯定是一個(gè) $\mathcal{P}(Q)\times \Sigma \to \mathcal{P}(Q)$ 的集合, 顯然這個(gè)轉(zhuǎn)移是確定的, 因?yàn)槊恳粋€(gè) $\mathcal{P}(Q)$ 中的元素都能夠被 $M$ 的一個(gè)狀態(tài)表示.
$M$ 的起始 $q_0^\prime$ 狀態(tài)是 $q_0$ 及 $q_0$ 能隨機(jī)轉(zhuǎn)移到的那些狀態(tài)構(gòu)成的集合.
$M$ 的接受狀態(tài)集是所有含有 $F$ 中任意元素的集合的集合.

通過(guò)這樣的轉(zhuǎn)換, 我們?nèi)菀鬃C明, $M(x)=1$ 當(dāng)且僅當(dāng) $N(x)=1$ .

正則語(yǔ)言與非確定自動(dòng)機(jī)

令人驚奇的是, 任何一個(gè)正則語(yǔ)言, 都能被一臺(tái)非確定自動(dòng)機(jī)判定, 而任何一臺(tái)非確定自動(dòng)機(jī)判定的語(yǔ)言都是正則語(yǔ)言. 我們不打算證明這一點(diǎn)(因?yàn)榻滩纳系淖C明非常詳細(xì)), 但是會(huì)介紹一下如何將一個(gè)正則語(yǔ)言轉(zhuǎn)換為判定它的非確定自動(dòng)機(jī).

定理

一個(gè)語(yǔ)言 $L$ 是正則語(yǔ)言, 當(dāng)且僅當(dāng)存在一臺(tái)非確定自動(dòng)機(jī) $Ｎ$ 可以判定它.

廣義非確定自動(dòng)機(jī)**. 廣義非確定自動(dòng)機(jī)是非確定自動(dòng)機(jī)的推廣版本, 它的定義和非確定自動(dòng)機(jī)類似. 唯一不同的一點(diǎn)在于, 其轉(zhuǎn)移函數(shù) $\delta$ 表示的映射是 $Q\times \Pi \to \mathcal{P}(Q)$ , 其中 $\Pi?$ 表示所有正則表達(dá)式的集合. 用通俗的語(yǔ)言來(lái)講, 它的狀態(tài)集圖上箭頭的標(biāo)號(hào)可以不僅是語(yǔ)言中的某個(gè)符號(hào), 而是可以是整個(gè)正則表達(dá)式. 我們已經(jīng)很清楚的知道, 每個(gè)正則表達(dá)式確實(shí)就是表示了某個(gè)正則語(yǔ)言, 因此, 廣義非確定自動(dòng)機(jī)的轉(zhuǎn)移是在讀取一個(gè)串后進(jìn)行的.

現(xiàn)在, 我們根據(jù)一個(gè)正則表達(dá)式可以做出最原始的廣義非確定自動(dòng)機(jī), 例如對(duì)正則表達(dá)式 $R$ , 我們可以作出狀態(tài)機(jī)圖 $q_0\overset{R}{\to}q_1$ . 其中 $q_0$ 是其實(shí)狀態(tài), $\{q_1\}$ 是接受狀態(tài)集. 我們考慮正則語(yǔ)言的三種操作, 將它表示轉(zhuǎn)移函數(shù)中的正則表達(dá)式僅有最基礎(chǔ)的三種正則表達(dá)式(即 $\varepsilon$ , $\emptyset$ , 單個(gè)符號(hào) $a$ )的廣義非確定自動(dòng)機(jī)(這其中 $\emptyset$ 標(biāo)注的轉(zhuǎn)移函數(shù)又可以略去不寫).

我們的任務(wù)很簡(jiǎn)單: 逐步將判定 $R?$ 的廣義非確定自動(dòng)機(jī) $G?$ 化為非確定自動(dòng)機(jī) $N?$ . 首先, 如果 $R?$ 是三種最平凡的正則表達(dá)式( $\emptyset?$ , 僅含一個(gè)單個(gè)符號(hào)的正則表達(dá)式, 正則表達(dá)式 $\varepsilon?$ )中的一種, 那么 $G?$ 就已經(jīng)是非確定自動(dòng)機(jī)了. 如果 $R?$ 是由兩個(gè)正則表達(dá)式 $R_1,R_2?$ 按照三種運(yùn)算( $\cup?$ , $\circ?$ , $\ast?$ )組成的, 那么我們按照以下方式處理.