資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚
法律研究構造以“a”開始但無子串“aab”的 DFA
問題
給定構造確定有限自動機 (DFA) 的語言是，字母表 ∑={a,b}，字串以“a”開頭但不包含子串“aab”。
解決方案
如果輸入為：“baabba”
輸出為：字串不被接受
因為該字串沒有以“a”開頭，並且生成了子串“abb”，
DFA 轉移圖
以“a”開頭但子串不為“aab”的字串的 DFA 轉移圖為 −
轉移表
轉移表如下 −
| 狀態 | 輸入 (a) | 輸入 (b) |
|---|---|---|
| → 0 | 1* | 4（死狀態） |
| 1* | 2* | 3* |
| 2* | 2* | 4（死狀態） |
| 3* | 1* | 3* |
| 4（死狀態） | 4（死狀態） | 4（死狀態） |
更新於: 15-Jun-2021
978 次瀏覽
廣告