為幫助考生備考軟考軟件設計師考試，希賽小編為大家整理了2022下半年軟件設計師知識點：有限自動機，相信對大家備考會有幫助。

有限自動機（★）

【考法分析】

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

【要點分析】

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

1）S是一個有限集，每個元素為一個狀態

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

3）δ是轉換函數：是一個單值對照

4）S0,屬于S，是其初態

5）Z是一個終態集（可空）

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

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

A．abab        B．aaaa       C．babb          C．abba

問題解析：

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

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

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

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

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

【備考點撥】

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

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

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