資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C語言程式構建接受奇數個0和1的DFA
構建用於語言L={w:w有奇數個0且w有奇數個1}的確定性有限自動機(DFA)，字母表Σ={0,1}。
示例
0111、010101、01110011是接受的字串，因為這些字串具有奇數個0和奇數個1。
對於給定的語言，我們需要四個狀態來繪製主要的DFA，它將讀取奇數個0和1。我們也可以透過合併兩個DFA來繪製它，其中一個只接受奇數個0，另一個接受奇數個1。
請按照以下步驟構建用於語言L={w:w有奇數個0且w有奇數個1}的DFA，字母表Σ={0,1} -
步驟1 - 對於奇數個0。
步驟2 - 對於奇數個1。
步驟3 - 將步驟1和步驟2結合起來，我們將得到最終結果。
解釋
讓我們以輸入01110011為例，首先從q0開始，輸入0時，它將進入狀態q1。
現在我們需要輸入1，然後它將進入狀態q3。
現在在q3上再次輸入1。它將進入狀態q1，然後再次輸入1，它將在讀取0111後到達q3。
現在輸入0，它將進入狀態q2，然後再次輸入0，它將進入狀態q3。
現在，當我們再次輸入1時，它將進入狀態q2。最後，在狀態q2上獲得輸入1後，它將到達狀態q3，這是最終狀態。
所以，字串被接受。
示例
以下是構建用於語言L={w:w有奇數個0且w有奇數個1}的DFA的C程式，字母表Σ={0,1} -
#include <stdio.h>
int EE=0, OE=1, OO=2, EO=3; // DFA states
int state = 0; // initial DFA state
char input;
int main(void) {
printf("Enter a string of 0s and 1s: ");
while (1) {
scanf("%c", &input);
if (input == '
') // if end-of-line exit loop
break;
if ( (input != '0') && (input != '1') ) { // invalid input printf("Invalid input: program terminating
");
break;
}
if (state==0) {
// input is either '0' or '1' state = (input == '0') ? OE : EO;
}
else if(state==1) {
state = (input == '0') ? EE : OO;
}
else if (state==2) {
state = (input == '0') ? EO : OE;
} else {
state = (input == '0') ? OO : EE;
}
};
if (input == '
') {
if (state == OO)
printf("Input accepted
");
else
printf("Input rejected
");
}
return 0;
}輸出
當我們執行上述程式時，我們將得到以下輸出 -
Run 1: Enter a string of 0s and 1s: 101010 Input accepted Run 2: Enter a string of 0s and 1s: 10011100 Input rejected
更新於: 2021年6月14日
9K+ 瀏覽量
廣告