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 28 = 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).
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); } %%
#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); }