CS 3723
 Programming Languages 
Simulating DFAs:
(a|b)*abb


DFA for (a|b)abb

The programs below (two in C and one in Java) recognize the language described by the regular expression (a|b)abb.

C program with gotos: This program almost directly mirrors the FSM. Each labeled location in the program corresponds to a state with a label. Each transition from one state to another corresponds to a goto between the associated locations, conditional on the symbol that is on the transition. This code is straightforward. It can't written this way in Java or Python because these languages don't have a goto.

C and Java programs using a while loop: These use a while loop to simulate the actions of the program with gotos. You have to study the code to understand it. The integer variable state keeps track of the current state. Of course it is initially 0 which is the start state here. Each iteration of the while loop corresponds to a single transition. The inner case handles each state separately.

C and Python programs using a while, and an extended if-else in place of a case: Many people feel that the case as it is in C or Java is perhaps the worst feature of these languages: terribly error-prone. Python has no case, so the extended if-else is the only option. Thus the middle program on the second row it the recommended model for you to use.

C Program, with gotos C Program, no gotos Java Program 
// abb0.c: recognize (a|b)*abb
#include <stdio.h>
void printit(int state, char ch);
int main() {
   char ch;
   L0: ch = getchar();
     printit(0, ch);
     if (ch == '$') goto L4;
     if (ch == 'a') goto L1;
     else if (ch == 'b') goto L0;
   L1: ch = getchar();
     printit(1, ch);
     if (ch == '$') goto L4;
     if (ch == 'a') goto L1;
     else if (ch == 'b') goto L2;
   L2: ch = getchar();
     printit(2, ch);
     if (ch == '$') goto L4;
     if (ch == 'a') goto L1;
     else if (ch == 'b') goto L3;
   L3: ch = getchar();
     printit(3, ch);
     if (ch == '$') goto L5;
     if (ch == 'a') goto L1;
     else if (ch == 'b') goto L0;
   L4: printf("Reject\n");
     return;
   L5: printf("Accept\n");
}

void printit(int state,char ch){
   printf("In state: %i,
      char=%c", state, ch);
   if (state == 3)
      printf(" Terminal");
   printf("\n");
}
// abb1.c: recognize (a|b)*abb
#include <stdio.h>

int main() {


  char ch;
  int state = 0;

  while (1) {
    ch = getchar();
    if (ch == '$') break; // while
    switch (state) {
    case 0: if (ch == 'a') state = 1;
       else if (ch == 'b') state = 0;
       break;
    case 1: if (ch == 'a') state = 1;
       else if (ch == 'b') state = 2;
       break;
    case 2: if (ch == 'a') state = 1;
       else if (ch == 'b') state = 3;
       break;
    case 3: if (ch == 'a') state = 1;
       else if (ch == 'b') state = 0;
       break;
    }
    printf("ch: %c, next state: %i",
       ch, state);
    if (state == 3)
       printf(" Terminal");
    printf("\n");
  }
  if (state == 3) printf("Accept\n");
  else printf("Reject\n");
}

// Abb0.java: recognize (a|b)*abb
import java.io.*;
public class Abb0 {
  public static void main(String[]
       args){
    GetChar getChar = new GetChar();
    char ch;
    int state = 0;
  
    while (true) {
      ch = getChar.getNextChar();
      if (ch == '$') break; // while
      switch (state) {
      case 0: if (ch == 'a') state = 1;
         else if (ch == 'b') state = 0;
         break;
      case 1: if (ch == 'a') state = 1;
         else if (ch == 'b') state = 2;
         break;
      case 2: if (ch == 'a') state = 1;
         else if (ch == 'b') state = 3;
         break;
      case 3: if (ch == 'a') state = 1;
         else if (ch == 'b') state = 0;
         break;
      }
      System.out.print("ch: " + ch + ",
         next state: " + state);
      if (state == 3)
         System.out.print(" Terminal");
      System.out.print("\n");
    }
    if (state == 3)
      System.out.print("Accept\n");
    else System.out.print("Reject\n");
  }
}
// GetChar.java for input
// Version without everything in main

C , no case but if-then-else Python Python (not using stdin) 
// aab.C: simulate aab fsm
#include <stdio.h> 

int main() {
   char ch;
   int state = 0;
   while (1) {
      ch = getchar();
      if (ch == '$')
         break;
      if (state == 0) {
         if (ch == 'a')
            state = 1;
         else if (ch == 'b')
            state = 0;
      }
      else if (state == 1) {
         if (ch == 'a') 
            state = 1;
         else if (ch == 'b') 
            state = 2;
      }
      else if (state == 2) {
         if (ch == 'a') 
            state = 1;
         else if (ch == 'b') 
            state = 3;
      }
      else if (state == 3) {
         if (ch == 'a') 
            state = 1;
         else if (ch == 'b') 
            state = 0;
      }
      printf("ch: %c, next state: %i",
          ch, state);
      if (state == 3)
         printf(" Terminal");
      printf("\n");
   }
   if (state == 3)
      printf("Accept\n");
   else
      printf("Reject\n");
}
 
# aab.py: simulate aab fsm
import sys
def getch():
    c = sys.stdin.read(1)
    if len(c) > 0:
        return c
    else:
        return None



state = 0
while True:
    ch = getch()
    if ch == '$':
        break
    if state == 0:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 0
    elif state == 1:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 2
    elif state == 2:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 3
    elif state == 3:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 0
    sys.stdout.write("ch: " + ch +
      ", next state: " + str(state))
    if state == 3:
        sys.stdout.write(" Terminal")
    sys.stdout.write("\n")
    
if state == 3:
    sys.stdout.write("Accept\n")
else:
    sys.stdout.write("Reject\n")

# aab.py: simulate getch
import sys
def getch():
    global i
    s = "ababaabbaababba$"
    if i >= len(s) - 1:
        return None
    i = i + 1
    return s[i]

i = -1
state = 0
while True:
    ch = getch()
    if ch == '$':
        break
    if state == 0:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 0
    elif state == 1:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 2
    elif state == 2:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 3
    elif state == 3:
        if ch == 'a':
            state = 1
        elif ch == 'b':
            state = 0
    sys.stdout.write("ch: " + ch +
      ", next state: " + str(state))
    if state == 3:
        sys.stdout.write(" Terminal")
    sys.stdout.write("\n")
    
if state == 3:
    sys.stdout.write("Accept\n")
else:
    sys.stdout.write("Reject\n")

Common Output
% python abb.py
ababaabbaababba$
ch: a, next state: 1
ch: b, next state: 2
ch: a, next state: 1
ch: b, next state: 2
ch: a, next state: 1
ch: a, next state: 1
ch: b, next state: 2
ch: b, next state: 3 Terminal
ch: a, next state: 1
ch: a, next state: 1
ch: b, next state: 2
ch: a, next state: 1
ch: b, next state: 2
ch: b, next state: 3 Terminal
ch: a, next state: 1
Reject
     Each of the 6 programs above produce exactly the same output, which is shown at the left. The first 5 run at the command line using ababaabbaababba$ as command line input. The compile and run lines for C and Java are (% = command line prompt) as follows. (Of course you might use a development environment for Java, such as DrJava or Eclipse.)

       
% cc -o abb1 -Wall abb1.c
% ./abb1
ababaabbaababba$
           
% javac Abb.java
% java Abb
ababaabbaababba$
The sixth program (directly above at the right) would also run if there was a problem using stdin. Runs:

  • Both Python programs ran using the compileonline Python 3 simulator. In the first Python program I was able to specify the input from stdin.
  • Both Python programs ran using the ideone Python 3 simulator. In the first Python program I was able to specify the input from stdin.
  • The second Python program ran using the appspot Python 3 simulator and the tutorialspoint Python 2.7.4 simulator. (Neither one allows for stdin.)

( Revision date: 2014-08-20. (Please use ISO 8601, the International Standard.)