有限状态自动机编程练习1

• 题目: 请设计DFA, 在任何由0, 1构成的串中, 接受含有01字串的全部串.

解:

DFA可能出现三个状态:

1. q1: 未发现01, 即扫描了那么多字符, 还没发现0, 换言之0从未出现.
2. q2: 未发现01, 但刚刚读入的字符是0.
3. q3: 已经发现01, 该状态也是终结状态(accept state).

它们的状态转移图如下:

编写程序, 运行效果如下:

测试用例说明:

1. 0000不被上图的DFA接受
2. 1111不被上图的DFA接受
3. 0101符合题目要求, 被DFA接受
4. 00111100011101符合题目要求, 被DFA接受
5. 空串不被DFA接受

程序代码如下:

/* FSM-example1.c
 * Using Deterministic Finite Automaton to recongnize
 *   a `0-1 string`
 *
 * Example1: Please design a DFA, accept every string 
 *   containing 01 substring.
 **/

#include <stdio.h>
#include <stdlib.h>     // calloc(), exit()

enum {
    STATE_1 = 1,    // 01 not found, which means 0 hasn‘t appeared yet
    STATE_2,        // 01 not found, but just read a 0
    STATE_T         // 01 has found, the 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(fsm_st));
    myFsm->state = STATE_1;
    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("\t--------Accept string!--------\n");

    free(myFsm);
    return 0;
}

void FSMdriver(fsm_st* me) {
    int pos = me->pos;
    switch(me->state) {
        case STATE_1:
            if( me->buf[pos] == ‘1‘ ) {
                me->state = STATE_1;
                me->pos++;
            } else if( me->buf[pos] == ‘0‘ ) {
                me->state = STATE_2;
                me->pos++;
            } else {
                me->state = STATE_T;
                Hault(STATE_1);
            }
            break;

        case STATE_2:
            if( me->buf[pos] == ‘0‘ ) {
                me->state = STATE_2;
                me->pos++;
            } else if( me->buf[pos] == ‘1‘ ) {  // Terminated correctly
                me->state = STATE_T;
            } else {
                me->state = STATE_T;
                Hault(STATE_2);
            }
            break;

        case STATE_T:
            break;
    }
}

void Hault(int s) {
    printf("\txxxxxxxx-FSM hault in STATE_%d-xxxxxxxx\n", s);
    free(myFsm);
    exit(0);
}

DFA编程练习1

原文：https://www.cnblogs.com/laplaceB/p/14318698.html