C program that reads the description of a deterministic finite automaton and builds it

Question

I just got done coding this C program:

Read the description of a deterministic finite automaton from standard input.

The first line of input is the number of states in the automaton, n

n lines follow, each one describing a state. Each line is composed of the name of the state, followed by its transitions, colon-separated. A transition is indicated like (S,c) and means that the automaton will move to state S upon reading the character c.

If the name of a state begins with F, it's a terminal state. For example, F1;(A,b);(C,d) is a terminal state and the automaton will move to state A upon reading characer b, and to state C upon reading character d. The name of a state can be 10 characters long at most.

After having read all the states, the program will read lines of text from standard input, until the line STOP is input. For every line, the automaton will determine if it belongs to the described language and, if it does, will echo it back.

Note: the program must not print anything but the recognized lines to standard output.

I thought it was an interesting problem. A few notes:

1. There are no error messages to handle ill-formed input. We were required by those who gave us the assignment to focus on solving the problem, rather than making it become an input-checking exercise. So I'll pretty much assume the input is well-formatted throughout the program

2. There are no prompt texts like Number of states? due to the program being corrected by an automatic platform that matches the exepcted output with the one from the program.

My program passed the tests on that platform so it works. What I'm interested in is, what could I have done to improve the code? Thank you!

Code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define SNL 10 // maximum number of characters in a state's name

typedef struct transition {
    char c;
    char *newState;
    struct transition *nextPtr;
} Transition;

typedef struct state {
    char *sName;
    Transition *tList;
} State;

int getNStates() { // gets the number of states in the automaton
    int n;
    
    if(scanf("%d", &n) != 1 || n <= 0) {
        exit(1);
    }
    
    return n;
}

State *createNewState(char stateName[]) { // creates a new state with the specified name and returns it
    State *newState = malloc(sizeof(State));
    if(newState == NULL) exit(1);
    
    newState->sName = malloc(sizeof(char) * SNL);
    if(newState->sName == NULL) exit(1);
    
    strcpy(newState->sName, stateName);
    newState->tList = NULL;
    
    return newState;
}

void appendTransition(Transition **tList, char *newS, char ch) { // appends a new transition to the existing list, recursively
    if(*tList == NULL) {
        *tList = malloc(sizeof(Transition));
        if(tList == NULL) exit(1);
        
        (*tList)->newState = malloc(sizeof(char) * strlen(newS)); // allocate memory for new state's name
        if((*tList)->newState == NULL) exit(1);
        
        strcpy((*tList)->newState, newS); // initialize new transition
        (*tList)->c = ch;
        (*tList)->nextPtr = NULL;
    } else {
        appendTransition(&((*tList)->nextPtr), newS, ch);
    }
}

State *move(State **automaton, int nStates, State *currState, char ch) { // returns a state if transition is found, NULL is no transition is found
    Transition *tList = currState->tList;
    if(tList == NULL) return NULL;
    
    while(tList != NULL) {
        if(tList->c == ch) { // found correct transition
            for(size_t i = 0; i < nStates; i++) {
                if(!strcmp(automaton[i]->sName, tList->newState)) { // find the correct state in the table
                    return automaton[i];
                }
            }
        }
        tList = tList->nextPtr;
    }
    
    return NULL;
}

int evaluate(State **automaton, int nStates, char *line) {
    if(*automaton == NULL) {
        return 1;
    }
    
    State *st = automaton[0]; // initial state is the first state
    
    for(size_t i = 0; i < strlen(line); i++) {
        st = move(automaton, nStates, st, line[i]); // transition to the next state
        if(st == NULL) {
            return 0;
        }
    }
    
    if(st->sName[0] == 'F') { // if state name begins with 'F', it's a terminal state
        return 1;
    }
    
    return 0;
}

int main() {
    int n = getNStates();
    
    char stateName[SNL]; // used to store current state's name
    char newState[SNL]; // used to store newState's name for every transition
    char c; // used to store character that leads to newState for every transition
    char line[100]; // used to store current line of text
    
    State **automaton = malloc(n*sizeof(State)); // create the automaton table
    if(automaton == NULL) exit(1);
    
    while(getchar() != '\n'); // clear buffer
    
    for(size_t i = 0; i < n; i++) { // get as many lines of text as there are states
        scanf("%[^\n]", line);
        
        automaton[i] = malloc(sizeof(State)); // allocate memory for new state
        if(automaton[i] == NULL) exit(1);
        
        char *token = strtok(line, ";"); // first token is the state name
        automaton[i]->sName = malloc(sizeof(char) * (strlen(token) + 1)); // allocate memory for state name
        if(automaton[i]->sName == NULL) exit(1);

        strcpy(automaton[i]->sName, token); // copy state name into the table
        automaton[i]->tList = NULL; // initialize current state transition table

        while(token = strtok(NULL, ";")) { // keep reading as long as there are transitions
            sscanf(token, "(%[^,],%c)", newState, &c);
            appendTransition(&(automaton[i]->tList), newState, c); // append new transition to state's list
        }
        while(getchar() != '\n'); // clear buffer
    }
    
    scanf("%100s", line); // read a line
    while(strcmp(line,"STOP")) { // keep reading lines until you encounter "STOP"
        if(evaluate(automaton, n, line)) { // print the line of text if it's recognized by the automaton
            puts(line);
        }
        scanf("%100s", line); // read a line
    }
    return 0;
}

Example inputs/outputs:

test case 1

input:
5
A;(A,a);(B,c)
B;(A,a);(C,b);(B,c);(F2,k)
C;(F1,d);(A,a);(B,c)
F1;(C,b)
F2;
akcdbbbbc
cacack
cacbd
STOP

output:
cacack
cacbd

test case 2

input:
3
S1;(S1,b);(S2,a)
S2;(S1,f);(F1,d);(S2,c)
F1;(S2,e);(F1,x)
bbafacccdedxxedx
x
bad
STOP

output:
bbafacccdedxxedx
bad

test case 3

input:
1
F1;(F1,a)
a
aaa
bad
ab
STOP

output:
a
aaa

Answer 1

About your notes

There are no error messages to handle ill-formed input. We were required by those who gave us the assignment to focus on solving the problem, rather than making it become an input-checking exercise. So I'll pretty much assume the input is well-formatted throughout the program

It is a good excercise for yourself to add input checking. Invalid input is rather common, and if you don't check it, your program might crash (which is actually the best possible outcome), or worse: the program seems to run fine but you might get incorrect results.

There are no prompt texts like Number of states? due to the program being corrected by an automatic platform that matches the exepcted output with the one from the program.

That's actually a good thing, if it's more likely that someone will pipe a file to the program's standard input instead of typing in manually while the program is running.

Allocate a whole array in one go

You are creating an array of pointer to States, and then while reading each line of input, you allocate the actual memory for each individual State. You can just as well allocate the memory for all States in one go:

State *automaton = malloc(n * sizeof(*automaton));

Note that sizeof(*automaton) is equal to sizeof(State), but prefer to use an actual variable to get the size of a type. The advantage of the former is that if you ever change the type of automaton, that you only have to do it in one place instead of multiple places.

In the for-loop, you can now just use . instead of -> to access the array members.

Prefer strdup() over manual allocation + copying of strings

While it's not part of the C standard, POSIX.1-2001-compliant C libraries provide a function named strdup() that will copy a string for you. So instead of doing a malloc() and strcpy(), you could write:

automaton[i].sName = strdup(token);

Note how you no longer have to check the length of the string manually. This would fix the bug in appendTransition(), where you forgot to add + 1 to the length of the string when calling malloc().

Enable compiler warnings and fix all warnings it prints

Even if the warnings seem harmless, do fix them. It usually just ensures you keep your code clean (like getting rid of the unused stateName variable), but some warnings might actually point to potential bugs in your program.

Use fgets() to read lines

Instead of using scanf() and getch() to read lines, I recommend you use fgets() instead. It's designed to read in complete lines. The only issue that you have to deal with is that it stores the newline character (\n) in the destination string as well. Also make sure that you pass the correct size of the buffer. For example:

fgets(line, sizeof(line), stdin); // Please do check the return value of fgets()!
size_t len = strlen(line);
if (len && line[len - 1] == '\n')
    line[len - 1] = '\0'; // Removes trailing newline.

Consider not hardcoding the check for terminal states in evaluate()

It would make evaluate() simpler to maintain and more flexible if you didn't hardcode the knowledge that state names starting with "F" indicate terminal states. Instead, create another function to check this, and call that inside evalute() like so:

if(is_terminal(st))
    return 1;

Note that you don't need the comment anymore explaining what that if-statement does. Then you can decide how to implement is_terminal(). You can move the check for the name there:

bool is_terminal(const State *st) {
    return st->sName[0] == 'F';
}

Use const where appropriate

Whenever a variable is not supposed to be changed after being initialized, add const to its declaration. For example, if you use strdup() as mentioned above, you could make the strings stored in Transition and State const, like so:

typedef struct transition {
    char c;
    const char *newState;
    struct transition *nextPtr;
} Transition;

typedef struct state {
    const char *sName;
    Transition *tList;
} State;

And functions that take a string argument should be annotated as well, for example:

State *createNewState(const char *stateName) {
    ...
    newState->sName = strdup(stateName);
    ...
}

Once you have parsed the state definitions from the input, the functions that evaluate the automaton should not modify them. So you should be able to write the following (assuming you allocated memory for states using a single malloc() call):

const State *move(const State *automaton, int nStates, const State *currState, char ch) {
    ...
}

int evaluate(const State *automaton, int nStates, const char *line) {
    ...
}

The const annotation will allow the compiler produce better optimized code, and will generate errors when you accidentally do try to write to them.

Use static where appropriate

Functions and variables that are only used in the same .c-file where they are defined should be made static. This helps the compiler produce more optimized code, and prevents namespace pollution in larger projects. If you have everything in one .c-file, then every function and every global variable can be made static, except main() itself.

Improving performance

Your function move() is quite inefficient, it scales as O(S+T), where S is the number of states and T the number of possible transitions per state. It is possible to turn this into an O(1) operation. Instead of having a linked list of transitions, each storing the name, you could have an array of pointers to States, indexed by the input character, like so:

typedef struct state {
    const char *sName;
    State *transitions[128]; // handle all 7-bit ASCII characters
} State;

Assuming you fill in the transitions array correctly when parsing the state definitions, you can then change move() to:

const State *move(const State *automaton, int nStates, const State *currState, char ch) {
    return currState->transitions[ch];
}

This solution is very fast, but it might waste quite a bit of memory if you only have a few valid transitions per state.

Note that the above solution didn't require comparing state names. You could avoid that in your solution as well, by using struct state *newState in Transition, instead of storing the state name. Of course, the reason you went for this solution is that it simplifies parsing of the state definitions. However, it should be easy to modify the state definition parser to also handle previously unseen states after the first ;.

Answer 2

Overall good job, the code checks malloc() and sometimes checks scanf() for errors, generally braces wrap logic in if statements and loops. The functions generally adhere to the Single Responsibility Principle.

It's not clear why the function createNewState() is unused since this would greatly simplify the main() function.

There should be a function createNewTransition() that handles creating a transition, this would simplify the code in void appendTransition(Transition **tList, char *newS, char ch).

Recursion isn't necessary in void appendTransition(Transition **tList, char *newS, char ch), it is very easy in a while loop to find the last transition in the list.

Readability

The structure/type names are good because they are descriptive.

Since stdlib.h already has to be included for malloc(), it might be better to use EXIT_SUCCESS and EXIT_FAILURE as the exit status.

int main() {

...

    if(automaton == NULL) exit(EXIT_FAILURE);

    ...

    return EXIT_SUCCESS;
}

The variable name n isn't as descriptive as it could be, since the function to get the number of states is called getNStates() the variable could be called nStates.

Keep the User Informed

The program does not prompt the user for input even though it expects user intput, and the program does not report errors, it only quits when there are errors.

The user should be prompted for input and error reporting should be added to error handling.

void  reportErrorAndQuit(char *emsg)
{
    fprintf(stderr, emsg);
    exit(EXIT_FAILURE);
}

int readNStates(){
    int nStates = 0;

    printf("Please enter the number of states in the automaton, the number of states must be greater than zero.\n");

    int scanfStatus = scanf("%d", &nStates);
    if (scanfStatus < 1 || scanfStatus == EOF) {
        reportErrorAndQuit("Unable to read input, exiting program\n");
    }

    return nStates;
}

int getNStates() { // gets the number of states in the automaton
    int nStates = 0;

    while  (nStates <= 0) {
        nStates = readNStates();
    }

    return nStates;
}

Calling exit()

It is not necessary to call exit(int exitStatus) from main() a simple return exitStatus; is what is generally used. Call exit() from functions other than main() since the other functions don't return values to the operating system.

Reading a Line of Input From stdin

The C library provides 2 functions for reading a line of input which might be better than using scanf("%[^\n]", line);. These functions are fgets(char *input_buffer, int max_buffer_size, FILE *stream) and gets(char *input_buffer). The function fgets() is considered safer since the buffer size is known and there will be no buffer overflow.

        size_t charsRecieved = fgets(line, 100, stdin);
        if (size_t < 1) reportErrorAndQuit("Can't line read input from stdin\n");

There is a constant defined in stdio.h which is often used with fgets(), this constant is BUFSIZE and it is system dependent, generally the largest line that can be read.

If the function fgets() is used then the code doesn't have to clear the input buffer after scanf().

State *move(State **automaton, int nStates, State *currState, char ch)

In this function the line

    if(tList == NULL) return NULL;

is not necessary, the condition in the while loop will handle this case, if tList is NULL it the code will not enter the loop.