Fall 2000, CSE 468: Solution of Assignment 2

Exercise 1

One possible solution is: (a+b)*bba*.

Exercise 2

Exercise 3

We construct the NFA directly (not from the previous NFA-lambda)

Exercise 4

Exercise 5

We give the solution in C.

#include <stdio.h>
#include <string.h>

int main() {
   char crt_symb; /* The current input symbol */
   int crt_state; /* The current state. The states will be represented by 0,1,2,3 */
   int delta[4][2] = {{0,1},
                      {0,2},
                      {3,2},
                      {3,1}}; /* The transition relation. The rows represent the 
                                 states, the colums represent the input symbols
                                 a and b respectively */
   int col; /* Integer which will represent the column associated to a (0) and b (1) */

   crt_state = 0; /* The initial state is 0 */
   printf("Enter the input string on the alphabet {a,b} \n(type c to mark the end of the input): ");
   scanf("%c", &crt_symb);
   
   while (crt_symb != 'c') {
       if (crt_symb == 'a')
           col = 0;
       else 
           col = 1;
       crt_state = delta[crt_state][col];
       scanf("%c", &crt_symb);
   }
 
   if (crt_state == 2 || crt_state == 3) 
       printf("Input string accepted \n");
   else
       printf("Input string rejected \n");          
}