2022年軟件設計師考試知識點（七十）：有限自動機

很多考生在備考2022年軟件設計師考試，希賽小編為大家整理了2022年軟件設計師考試知識點（七十）：有限自動機，供考生備考復習。

有限自動機（★）

【考法分析】

1、本知識點的主要考查形式有：給出一個確定或不確定的有限自動機，指出其能夠識別的字符串，或指出對應的正規(guī)式表示。

【要點分析】

1、定義：M=(S,∑, δ,S0,Z)

1）S是一個有限集，每個元素為一個狀態(tài)

2）∑是一個有窮字母表，每個元素為一個輸入字符

3）δ是轉(zhuǎn)換函數(shù)：是一個單值對照

4）S0,屬于S，是其初態(tài)

5）Z是一個終態(tài)集（可空）

2、一個有限自動機所識別的語言是從開始狀態(tài)到終止狀態(tài)所有路徑上的字符串的集合。要判斷一個字符串能否被指定的自動機識別，就看在該自動機的狀態(tài)圖中能否找到一條從開始狀態(tài)到達終止狀態(tài)的路徑，且路徑上的字符串等于需要識別的字符串。而對于其正規(guī)式，可以通過能夠識別的字符串去總結規(guī)律。

例：下圖所示的有限自動機中，s0是初始狀態(tài)，s3為終止狀態(tài)，該自動機不能識別（）。

A．a(chǎn)bab        B．a(chǎn)aaa       C．babb          C．a(chǎn)bba

問題解析：

一個有限自動機所識別的語言是從開始狀態(tài)到終止狀態(tài)所有路徑上的字符串的集合。要判斷一個字符串能否被指定的自動機識別，就看在該自動機的狀態(tài)圖中能否找到一條從開始狀態(tài)到達終止狀態(tài)的路徑，且路徑上的字符串等于需要識別的字符串。

對于字符串“abab”，其識別路徑為s0→s1→s2→s1→s2，字符串結束時的狀態(tài)不是終止狀態(tài)，所以該自動機不能識別“abab”。

對于字符串“aaaa”，其識別路徑為s0→s1→s3→s3→s3，字符串結束時的狀態(tài)是終止狀態(tài)，所以該自動機可以識別“aaaa”。

對于字符串“babb”，其識別路徑為s0→s2→s1→s2→s3，字符串結束時的狀態(tài)是終止狀態(tài)，所以該自動機可以識別“babb”。

對于字符串“abba”，其識別路徑為s0→s1→s2→s3→s3，字符串結束時的狀態(tài)是終止狀態(tài)，所以該自動機可以識別“abba”。

【備考點撥】

1、掌握有限自動機相關的基本概念；

2、掌握有限自動機能夠識別的字符串判斷；

3、掌握有限自動機與正規(guī)式的對應關系。