dfa2.java 原理_DFA编程练习2
題目: 請設計DFA, 使其接受全部含有奇數個1的串, 假定 ∑ = {0, 1}.
解:
DFA可能出現兩個個狀態:
qeven: 讀入了偶數個1的串.
qodd: 讀入了奇數個1的串, 該狀態也是終結狀態(accept state).
它們的狀態轉移圖如下:
編寫程序, 運行效果如下:
測試用例說明:
0000不被上圖的DFA接受
1111不被上圖的DFA接受
1符合題目要求, 被DFA接受
0011001符合題目要求, 被DFA接受
空串不被DFA接受
0不被上圖DFA接受
程序代碼如下:
/* FSM-example2.c
* Using Deterministic Finite Automaton to recongnize
* a `0-1 string`
*
* Example2: Please design a DFA, accept every string
* containing odd numers of 1.
**/
#include
#include // calloc()
#include
enum {
STATE_even = 1, // Even number of 1 has readed
STATE_odd, // Odd number of 1 has readed
STATE_T // Accept state
};
typedef struct fsm_st {
int state;
int pos; // point to current pos
char buf[BUFSIZ];
}fsm_st;
fsm_st* myFsm;
void FSMdriver(fsm_st*);
void Hault(int);
int main() {
/* Create a FSM and initialize */
myFsm = (fsm_st*)calloc(0x1, sizeof(myFsm));
myFsm->state = STATE_even;
myFsm->pos = 0;
/* Read a string */
printf("Input a 01-string: ");
fgets(myFsm->buf, BUFSIZ, stdin);
/* Strat FSM */
while( myFsm->state != STATE_T ) {
FSMdriver(myFsm);
}
printf("Accept string!
");
free(myFsm);
return 0;
}
void FSMdriver(fsm_st* me) {
int pos = me->pos;
switch(me->state) {
case STATE_even:
if( me->buf[pos] == ‘1‘ ) {
me->state = STATE_odd;
me->pos++;
} else if( me->buf[pos] == ‘0‘ ) {
me->state = STATE_even;
me->pos++;
} else {
Hault(STATE_even);
}
break;
case STATE_odd:
if( me->buf[pos] == ‘0‘ ) {
me->state = STATE_T; // Terminated correctly
me->pos++;
} else if( me->buf[pos] == ‘1‘ ) {
me->state = STATE_even;
me->pos++;
} else {
me->state = STATE_T; // At the end stay in STATE_odd
}
break;
}
}
void Hault(int s) {
printf("FSM hault in STATE_%d
", s);
printf("FSM don‘t accept this string
");
free(myFsm);
exit(0);
}
DFA編程練習2
總結
以上是生活随笔為你收集整理的dfa2.java 原理_DFA编程练习2的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 四川阿坝州11连震 最高6.0级暂无人员
- 下一篇： 老外绘制预装iOS 16的iPhone