Simple Infinite automaton [C]

时间:2023-11-23 16:29:56

Today I read the book Formal Language and Automaton Theory.
And I learnt the infinite automaton.
Here is an image from the book:

Simple Infinite automaton [C]


I wrote a simple program to realize it:

/**
 * Program:
 *  Limited State Automatic Machine
 * Date:
 *  2016-03-22
 * Author:
 *  brant-ruan
 * Principle:
 *  S -> aA|aB
 *  A -> aA|c
 *  B -> aB|d
 **/
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1

/* Machine state */
enum state{
    q0, q1,
    q2, q3
}crtStat;

/* Judge whether state translation is valid */
int JudgeValid(int stat1, char c)
{
    switch(stat1){
    case q0:
        if(c == 'a')
            crtStat = q1;
        else
            return ERROR;
        break;
    case q1:
        if(c == 'c')
            crtStat = q2;
        else if(c == 'd')
            crtStat = q3;
        else if(c != 'a')
            return ERROR;
        break;
    case q2:
    case q3:
    default:
        return ERROR;
        break;
    }
}

int main()
{
    char c; // character inputted
    crtStat = q0; // Initialize state to q0

    while(((c = getchar()) != EOF) && (c != '\n')){
        if((c != 'a' && c != 'c' && c != 'd') ||
                JudgeValid(crtStat, c) == ERROR){
            printf("Not exist.\n");
            exit(0);
        }
    }
    if(crtStat != q2 && crtStat != q3)
        printf("Not exist.\n");
    else
        printf("Exist.\n");

    exit(0);
}