Implementing a Finite State machine in C

2
votes

I have been writing a code that either accepts or rejects a string of input symbols as part of a specified language. And I have written code for the first language but it doesn't accept the right thing and i was wondering if any one could give me a hint as to where i went wrong. thanks

Question: Why wont the language be accepted or rejected correctly?

Thanks

My code: 

#include <stdio.h>

static final char initial_state = '0';
static final char 0 = '0';
static final char 1 = '1';
static final char 2 = '2';
static final char 3 = '3';

int main(int argc, char* argv[]){
  int x;
  char current_state, next_state, initial_state;
  current_state = initial_state;

  printf("Enter a string of characters: ");
  while(scanf("%d", &x)!=EOF){
     switch(current_state){
      case 0: /*initial state*/
       switch(current_state){
       case'0':next_state=1; break;
       case'1':next_state=0; break;
       }
       break;
     case 1: /*Last input was 0*/
      switch(current_state){
      case'0':next_state=1; break;
      case'1':next_state=2; break;
      }
      break;
     case 2: /*Last input was 1*/
      switch(current_state){
      case'0':next_state=3; break;
      case'1':next_state=0; break;
      }
      break;
     case 3: /*Last input was 0*/
      switch(current_state){
      case'0':next_state=3; break;
      case'1':next_state=3; break;
      }
      break;
     }
     current_state=next_state;
    }
  if((current_state==next_state)){
    printf("Language 1 accepts");
  }else if((current_state!=next_state)){
    printf("Language 1 rejects");
  }
  return 0;
}
4
cprojectstate-machine
An English description of 'Language1' would be most helpful in diagnosing why the Code does not match the Language - ford
final in c? when did that get there? I've been playing with SQL in recent years instead :) - Poodlehat
Language one is defined by accepting 010 and to get the the accepted state the last character can either be a 0 or a 1. - Cka91405
@Poodlehat I'm not too sure what you are seeing, could you be more specific please. Thank you - Cka91405
Does this code compile? With a variable named 0? - Doug Currie

4 Answers

2
votes

You're setting initial state as a character zero and not a numeric zero. Try this instead:

static final char initial_state = 0;
2
votes

You are only switching on current_state and not the input.

1
votes

You have defined initial_state twice, and the local one is winning the "scope war." So in your code, every time you think you're referring to this initial_state:

static final char initial_state = '0';

you're actually referring to this initial state:

char current_state, next_state, initial_state;  // this last guy here

Additionally, you're doing some numerics and some characters. You want all characters since you're taking input from the keyboard. Any place that you define a state as a 1 or a 0, put single quotes around it so it's a '1' or a '0'.

Then, take out the code that redefines 1 = '1' for all the states; I do believe you're asking the program to redefine the number 0x1 to mean the number 0x41 -- that's crazy.

Here's the final result (badly formatted):

#include <stdio.h>

static const char initial_state = '0';
static const char accepting_state = '3';
int main(int argc, char* argv[]){
  int x;
  char current_state;

  current_state = initial_state;
  printf("Enter a series of characters (0 or 1)\n");
  printf("Press <ctrl-d> to finish.\n");
  printf("> ");
  while(scanf("%d", &x)!=EOF){
     x += '0';
         switch(current_state){
      case '0': /*initial state*/
       switch(x){
       case'0':current_state='1'; break;
       case'1':current_state='0'; break;
       default: goto fail;
       }
       break;
     case '1': /*Last input was 0*/
      switch(x){
      case'0':current_state='1'; break;
      case'1':current_state='2'; break;
      default: goto fail;
      }
      break;
     case '2': /*Last input was 1*/
      switch(x){
      case'0':current_state='3'; break;
      case'1':current_state='0'; break;
      default: goto fail;
      }
      break;
     case '3': /*Last input was 0*/
      switch(x){
      case'0':current_state='3'; break;
      case'1':current_state='3'; break;
      default: goto fail;
      }
      break;
     default: goto fail;
     }
     printf("> ");
  }

  if (current_state == accepting_state) {
    printf("Language accepts!\n");
  } else {
    printf("Language rejects.\n");
  }
  return 0;

fail:
  printf("Invalid input\n");
  return 1;
}
1
votes

Since the inner switch is a char, I believe you meant it to be on x and not current_state:

 switch(current_state){
  case 0: /*initial state*/
   switch(x){
   case'0':next_state=1; break;
   case'1':next_state=0; break;
   }
   break;