資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C程式構建接受以“01”結尾的語言的DFA
問題
設計一個確定性有限自動機 (DFA)，其∑ = {0, 1}，接受字元集{0, 1}上以“01”結尾的語言。
解答
給定語言生成的字串如下：
L={01,001,101,110001,1001,……….}字串的最小長度為2，給定語言的DFA由以下狀態組成：2+1 = 3個狀態。
這裡：
q0 − 輸入0時，它進入狀態q1；輸入1時，它保持自身狀態。
q1 − 輸入0時，它保持自身狀態；輸入1時，它進入狀態q2。
q2 − 輸入0時，它進入狀態q1；輸入1時，它進入狀態q0。狀態q2是最終狀態。
示例
以下是構建DFA的C程式，其∑ = {0, 1}，接受字元集{0, 1}上以“01”結尾的語言：
#include
#define max 100
main() {
char str[max],f='a';
int i;
printf("enter the string to be checked: ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++) {
switch(f) {
case 'a': if(str[i]=='0') f='b';
else if(str[i]=='1') f='a';
break;
case 'b': if(str[i]=='0') f='b';
else if(str[i]=='1') f='c';
break;
case 'c': if(str[i]=='0') f='b';
else if(str[i]=='1') f='a';
break;
}
}
if(f=='c')
printf("
String is accepted", f);
else printf("
String is not accepted", f);
return 0;
}輸出
輸出結果如下：
Run 1: enter the string to be checked: 10101001 String is accepted. Run 2: enter the string to be checked: 10000010 String is not accepted.
更新於：2021年6月15日
14K+ 瀏覽量
廣告