Classroom practice: Finite State Machines.

Gábor Horváth / Zsolt Kohári · 2020.12.11.

Design of Finite State Machines.

1. FSM

Finite State Machines. The first step of the solution is always the design of the state transition diagram or state transition table: the design of the FSM. Once it is done the coding is very straightforward. Always stick to the FSM, in the code all activities and transitions of the FSM must be considered. Writing a code not according to the FSM is absolutely wrong, it will never work correctly. The same applies if you try to provide the code first then design the FSM…

Even if you start your design with a graph, which is very convenient for the human brain to follow state transitions, a state transition table must be created from it to clean things up. A table ensures better that no possible state transition was neglected in the graph. It is also advantageous for the coding.

2. What does the program do?

Answer the following questions:

#include <stdio.h>
#include <ctype.h>

int main(void) {
    int c;
    while ((c = getchar()) != EOF) {
        putchar(tolower(c));
    }
    
    return 0;
}
  1. What does the program do?
  2. Why is the variable of type int?
  3. Why do we need parenthesis arund assignment?
  4. Why do we assign from tolower(c)?
  5. Will it work for digits and other symbols? Why?
  6. Can we use scanf–printf for the same purpose? How?

Solution

  1. Reads text from standard input and prints it to standard output in lowercase letters.
  2. Because getchar() may return EOF, which value can not be represented in a char.
  3. Because comparison has higher precedence than assignment.
  4. There are two options: take the parameter by address (&c), or return the modified value. The designers of the C library opted for the latter as it is simpler to use it this way.
  5. Yes, because tolower() returns them unaltered.
  6. Yes, like this: 
    char c;
while (scanf("%c", &c) == 1) {
    printf("%c", tolower(c));
}
    The variable must be char c in this case.

3. Sentence casing

Realize the 'reverse' of the previous task. Write a program that reads text in all lowercase letters and prints it using sentence casing; the very first character of each sentence must be uppercase. (The input cosists of lowercase letters, whitespace characters, in-sentence punctuation marks, and period, exlamation mark and question mark to denote the end of sentences. There is a whitespace in between two sentences.)

Solution

Finite state machine is necessary for the solution. After a punctuation mark denoting the end of sentence we can expect a whitespace and then the next letter character should be changed to uppercase. The whitespaces in between sentences should not prevent uppercasing the next letter. The base state is uppercasing as the very first character is the beginning of a sentence.

. ! ?space, \nother
uppercprint cprint cprint toupper(c)
→lowerc
lowercprint c
→endofsentence?		print cprint c
endofsentence?print cprint c
→upperc		print c
→lowerc 
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

bool end_of_sent(int c) {
    return c == '!' || c == '.' || c == '?';
}

int main(void) {
    enum states {
        upperc,
        lowerc,
        endsent
    } st;
    st = upperc;     /* base state */

    int c;
    while ((c = getchar()) != EOF) {
        switch (st) {
        case upperc:
            putchar(toupper(c));
            if (!end_of_sent(c) && !isspace(c))
                st = lowerc;
            break;
        case lowerc:
            putchar(c);
            if (end_of_sent(c))
                st = endsent;
            break;
        case endsent:
            putchar(c);
            if (isspace(c))
                st = upperc;
            else if (!end_of_sent(c))
                st = lowerc;
            break;
        }
    }

    return 0;
}