極簡計算機競賽切片系列7：ACSL第三輪FSA and RE

本篇是ACSL的第7篇，講述ACSL筆試中的

有限狀態自動機及正則表示式

相關知識點，這也是第三輪筆試中最後一個知識點。這部分內容相對來說比較抽象，但對我們瞭解一些高等的計算機概念比較有幫助，希望大家好好掌握。 此係列文章只涉及直接知識點，同學們在刷題和閱讀的過程中，有需要繼續深入的部分，請後臺留言，我會選擇一些跟進。

另外兩篇文章見：

極簡計算機競賽切片系列5：ACSL 第三輪Boolean Algebra

極簡計算機競賽切片系列6：ACSL第三輪Data Structure

I FSAs and Regular Expressions有限狀態自動機和正則表示式簡說

1. FSA有限狀態自動機

這個名字很奇怪的東西樣子是長這樣的：

其中：

圓圈：表示

狀態state

，所有的狀態組成

狀態集finite states set

，一個FSA中狀態數量有限，且每個時間點只有一個狀態是

活躍的active

無前驅箭頭的圓圈：表示

初始狀態start state

，只有一個，如上圖中的A

同心圓：表示

最終狀態final state

，可以有多個，組成的集合稱為

最終狀態集final states set

，如左上圖中的C，另外我們可以看到下圖中有兩個最終狀態

有前驅的箭頭：表示

轉移transition

，即從一個活躍狀態轉到另一個活躍狀態，箭頭上的字元表示

轉移規則transition rules

，或稱為轉移函式。所有出現的字元組成的集合叫做

字母表alphabet

，如上圖的字母表為

，下圖的字母表為

上圖兩圖的樣子是FSA的形象表示，而FSA的本質其實是一個

字串

的集合。 這個集合裡面的字串稱為

被這個FSA接受的

。

而什麼樣的字串才能被接受呢？

以上圖為例，決定過程如下：

從起始狀態A考察

透過

規則

方能啟用狀態B，而狀態B是進入最終狀態C的必經之路

從狀態B可以繼續根據

規則

再次啟用狀態B，如此重複若干次

從狀態B也可以直接透過

規則

啟用最終狀態C

到達最終狀態C後，還可以透過

規則

再次啟用最終狀態C，如此重複若干次

到達最終狀態，即為被此FSA接受

故透過以上分析，能被接受的字串不唯一，如有以下一些字串：

等等，這些所有被接受的字串的集合即為此FSA的本質。

上述字串集合，可以統一描述為如下形式：

+若干個（0個或有限多個）

+

+若干個（0個或有限多個）

。

表示出來是不是挺麻煩？為了簡化這種表示，給一類字串一個統一的單一表示，就需要引入下面

正則表示式

的概念。

2. Regular expression RE正則表示式

正則表示式可以看作FSA的代數表示，故也是一個

字串的集合

，這個集合中的

字串

就稱為

被這個RE接受的

，或者

被這個RE匹配的

。

只不過這個集合可以用一個統一代數表示方法表達出來。 為了達到此目的，我們需要引入字串的如下操作

操作定義

操作名

符號

意義

操作的優先順序

*

CONCATENATION

UNION

輔助符號

我們也可以借用括號輔助表示操作順序，如

。

如此一來，上述第一個能被FSA接受的字串，

+若干個（0個或有限多個）

+

+若干個（0個或有限多個）

，就可以用以上操作簡單的記為：

，即一個RE。

這也就完成了一個FSA和RE之間的轉化。

II FSAs and REs 真題實操

ACSL官方給出的考點如下，其中，中級基本不涉及FSA，初級兩者都不涉及。

Translate FSA to Regular Expression

Simplify Regular Expression

Determine if Regular Expressions are equivalent

Determine if a String is accepted by a Regular Expression or FSA

2018-2019 SENIOR DIVISION Contest #3 Q#5

注：要想被此FSA接受，將直箭頭上的字元寫出，圈箭頭上的字元則可以0或多次出現，另外，分叉處則可以選擇任一條路徑，即用

UNION

即可，結果如下：

2018-2019 INTERMEDIATE DIVISION Contest #3 Q#5

注：選最短字串，則

CLOSURE

取0次，

UNION

取較短的即可，如可以取：

，共9個字元。

2016-2017 Senior Division Contest #3 Q#5

注：此種類型的題目解題的關鍵是對照固定字元

本題RE必須以

開頭，故可以排除c）

然後我們看a），

可以透過，接下來的

可能屬於

，也可能屬於接下來的固定字元

如果是前者，則後面必須再跟個

如果是後者，其後只能跟若干個

或若干個

，故不可能

同理b）不可能

d）中，

後為

，則可能屬於

，也可能屬於其後的

如是前者，則其後跟的

必是

，而後

則是固定字元，後面的

屬於

，可以透過

最後看e），

後的

屬於

或

若屬於

，則

分別透過

和固定字元

，過後的字串只能是若干個

或若干個

，不能透過

若屬於

，也可排除，故e）不對。

現在能被接受的只有d）

以上的分析看起來比較繁瑣，其實是很快的。大家在練習的時候就知道了。

答案僅供參考，主要看分析方法，大致是不會錯的。對於大家發現的答案錯誤，還望告知，先拜謝。。。

兩天後就是第三輪比賽了，好好刷題吧。我們下次見...

如果需要一些題目增加練習量，可以後臺留言

至道

致力於做專業的

國際數學與計算思維

教育，歡迎關注交流

數學

，

程式設計

，

心理

，

宗教