KOI: Some solutions to exercise 6

Question 1

Example: If I move a physical volume knob or slider, I can move it as short a distance as I want, so on the scale from minimum value to maximum I can find an infinite number of positions. (There might be limitations on our physical reality, such as the Planck length, but let's ignore that for now.) Seen as a state machine, a volume slider has infinitely many states. If we measure the postions of the slider using an 8-bit integer, we can only represent 2⁸ = 256 different values, so if we see that as a state machine, it only has finitely many states.

b) A deterministic state machine can always determine which state to change to. A non-deterministic state machine can have several possible state transitions, and needs to "try them all in parallell" (or be rewritten as a determinstic state macine).

Question 2

Question 3

Question 4

b) Colon, semicolon, and the keywords began, candy, round, trick, treat, went and home.

c) Download: halloween.l

%{
    #include "halloween.tab.h"
%}

%%

[\n\t ] { /* Ignore whitespace */ }
"began" { return BEGAN; }
"candy" { return CANDY; }
"round" { return ROUND; }
"trick" { return TRICK; }
"treat" { return TREAT; }
"went"  { return WENT; }
"home"  { return HOME; }
[a-z]+  { printf("[WORD: '%s']", yytext); return WORD; }
";"     { return SEMICOLON; }
":"     { return COLON; }
.       { fprintf(stderr, "[Ignoring invalid character: '%c']\n", *yytext); }

%%

d) ...

Question 5

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "halloween.tab.h"

// Tokens from halloween.y
// %token BEGAN CANDY ROUND SEMICOLON TRICK TREAT COLON WORD WENT HOME

#define MAX_WORD_LENGTH 100

int yylex(void) {
    int c;

    c = getchar();

    // First, skip whitespace
    while (c == ' ' || c == '\t' || c == '\n')
        c = getchar();

    // Is it EOF
    if (c == EOF)
        return EOF;

    if (c == ':')
        return COLON;
    if (c == ';')
        return SEMICOLON;

    if (c >= 'a' && c <= 'z') {
        // This is the start of a word or a keyword
        char word[MAX_WORD_LENGTH + 1];
        int length = 0;
        word[length++] = c;
        while ((c = getchar()) >= 'a' && c <= 'z') {
            if (length >= MAX_WORD_LENGTH) {
                word[length] = '\0';
                fprintf(stderr, "Word too long: '%s'... (max is %d)\n", word, MAX_WORD_LENGTH);
                exit(EXIT_FAILURE);
            }
            word[length++] = c;
        }
        ungetc(c, stdin);
        word[length] = '\0';
        if (strcmp(word, "began") == 0)
            return BEGAN;
        else if (strcmp(word, "candy") == 0)
            return CANDY;
        else if (strcmp(word, "round") == 0)
            return ROUND;
        else if (strcmp(word, "trick") == 0)
            return TRICK;
        else if (strcmp(word,"treat") == 0)
            return TREAT;
        else if (strcmp(word, "went") == 0)
            return WENT;
        else if (strcmp(word, "home") == 0)
            return HOME;
        else
            return WORD;
    }

    fprintf(stderr, "Invalid input character: '%c' (%d)\n", c, c);
    exit(EXIT_FAILURE);
}