CS 327 Homework 1

Due Date

4:00 pm Friday September 18

Assignment Names

dfa

File Names

dfa1.c dfa2.c dfa3.c dfa.pdf

Draw DFAs that recognize the strings matching each of the following regular expressions and implement them using gotos. Use the program below as a guide.

Turn in the drawings in a single pdf file.

1. a*|b* (dfa1.c)
2. (a|b)*ab* (dfa2.c)
3. a*b*c* (dfa3.c)

Example DFA Implementation

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

int main() {
  char *line = NULL;
  size_t buffer_len = 0;
  ssize_t len;
  while ((len = getline(&line, &buffer_len, stdin)) != -1) {
    char *s = line;
    s1:
      switch (*s++) {
      case 'a': goto s1;
      case 'b': goto s2;
      default: goto reject;
      }
    s2:
      switch (*s++) {
      case '\n': goto accept;
      default: goto reject;
    }
  accept:
      printf("accepted\n");
      goto done;
  reject:
      printf("not accepted\n");
  done:
  }
  free(line);
}