設計一個NFA，其中Σ = {0, 1}，並接受所有長度至少為2的字串。

非確定有限自動機也具有五個狀態，與DFA相同，但具有不同的轉移函式，如下所示：

δ: Q X Σ -> 2Q

非確定有限自動機定義為一個五元組，

M=(Q, Σ, δ,q0,F)

其中，

• Q: 有限狀態集
• Σ: 有限的輸入符號集
• q0: 初始狀態
• F: 終結狀態
• δ: 轉移函式: Q X Σ -> 2Q

問題

為給定語言設計一個狀態轉換圖和狀態轉換表，該語言接受所有長度至少為2的字串。

解決方案

在繼續解決方案之前，讓我們瞭解一下字串長度的含義以及如何查詢任何字串的長度。

**字串長度**表示字串或單詞中符號的數量。它用|w|表示。

例如：w=01011001 來自二進位制字母表Σ={0,1}

|w| = 8

在給定的問題中，字串的長度至少應為2。也就是說，長度應為2或更大，但不能小於2，且字母表為Σ = {0, 1}。

語言L= { 00,01,10,11,001,110,101,111,000,1101,0010,…….}

狀態轉換圖

給定語言的NFA狀態轉換圖如下：

狀態轉換表

狀態轉換表如下：

解釋

• **步驟1** - q0是初始狀態，輸入'0'時它轉到狀態q1，輸入'1'時轉到狀態q1。
• **步驟2** - q1是中間狀態，輸入'0'和'1'時都轉到狀態q2。
• **步驟3** - q2是終結狀態，它包含ε轉移。

示例2

構造一個NFA，其中Σ = {0, 1}，它接受所有以01結尾的字串。

在給定的問題中，語言接受所有以01結尾的字串。

語言L= { 01,101,1101,001,11001,0101,11101,0001,1001,00101,…….}

狀態轉換圖

狀態轉換圖如下：

狀態轉換表

狀態轉換表如下：

解釋

• **步驟1** - q0是初始狀態，輸入'0'時它轉到多個狀態q0和q1，輸入'1'時它轉到狀態q0本身。
• **步驟2** - q1是中間狀態，輸入'1'時轉到狀態q2。
• **步驟3** - q2是終結狀態，它包含ε轉移。

Bhanu Priya

更新於: 2021年6月11日

18K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習