為幫助考生備考軟考軟件設(shè)計(jì)師考試，希賽小編為大家整理了2022下半年軟件設(shè)計(jì)師知識(shí)點(diǎn)：有限自動(dòng)機(jī)，相信對(duì)大家備考會(huì)有幫助。

有限自動(dòng)機(jī)（★）

【考法分析】

1、本知識(shí)點(diǎn)的主要考查形式有：給出一個(gè)確定或不確定的有限自動(dòng)機(jī)，指出其能夠識(shí)別的字符串，或指出對(duì)應(yīng)的正規(guī)式表示。

【要點(diǎn)分析】

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

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

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

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

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

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

2、一個(gè)有限自動(dòng)機(jī)所識(shí)別的語(yǔ)言是從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)所有路徑上的字符串的集合。要判斷一個(gè)字符串能否被指定的自動(dòng)機(jī)識(shí)別，就看在該自動(dòng)機(jī)的狀態(tài)圖中能否找到一條從開(kāi)始狀態(tài)到達(dá)終止?fàn)顟B(tài)的路徑，且路徑上的字符串等于需要識(shí)別的字符串。而對(duì)于其正規(guī)式，可以通過(guò)能夠識(shí)別的字符串去總結(jié)規(guī)律。

例：下圖所示的有限自動(dòng)機(jī)中，s0是初始狀態(tài)，s3為終止?fàn)顟B(tài)，該自動(dòng)機(jī)不能識(shí)別（）。

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

問(wèn)題解析：

一個(gè)有限自動(dòng)機(jī)所識(shí)別的語(yǔ)言是從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)所有路徑上的字符串的集合。要判斷一個(gè)字符串能否被指定的自動(dòng)機(jī)識(shí)別，就看在該自動(dòng)機(jī)的狀態(tài)圖中能否找到一條從開(kāi)始狀態(tài)到達(dá)終止?fàn)顟B(tài)的路徑，且路徑上的字符串等于需要識(shí)別的字符串。

對(duì)于字符串“abab”，其識(shí)別路徑為s0→s1→s2→s1→s2，字符串結(jié)束時(shí)的狀態(tài)不是終止?fàn)顟B(tài)，所以該自動(dòng)機(jī)不能識(shí)別“abab”。

對(duì)于字符串“aaaa”，其識(shí)別路徑為s0→s1→s3→s3→s3，字符串結(jié)束時(shí)的狀態(tài)是終止?fàn)顟B(tài)，所以該自動(dòng)機(jī)可以識(shí)別“aaaa”。

對(duì)于字符串“babb”，其識(shí)別路徑為s0→s2→s1→s2→s3，字符串結(jié)束時(shí)的狀態(tài)是終止?fàn)顟B(tài)，所以該自動(dòng)機(jī)可以識(shí)別“babb”。

對(duì)于字符串“abba”，其識(shí)別路徑為s0→s1→s2→s3→s3，字符串結(jié)束時(shí)的狀態(tài)是終止?fàn)顟B(tài)，所以該自動(dòng)機(jī)可以識(shí)別“abba”。

【備考點(diǎn)撥】

1、掌握有限自動(dòng)機(jī)相關(guān)的基本概念；

2、掌握有限自動(dòng)機(jī)能夠識(shí)別的字符串判斷；

3、掌握有限自動(dòng)機(jī)與正規(guī)式的對(duì)應(yīng)關(guān)系。