Finite State Machine In C

Question

I am trying to create a simple finite state machine in C and I'm quite confused on how to get started. I tried looking online but nothing has really cleared this up for me.

My goal is to check if a string is octal, hex or a decimal.

To be octal the string must start with a 0, followed by digits 0-7. To be hex the string must start with 0x or OX, followed by (a-f, A-F, 0-9)

My attempt at creating the states would be:

typedef enum  {
   ERROR,
   OCTAL,
   HEX,
   DECIMAL
} stringStates;

Now, I would then use a switch statement to go through the entirety of the string and switch between the different states until I have correctly identified which state it belongs to.

 while (current_Position<=end_String-1)
 {
    switch( "input something here")
      {
        case 0:
             //process string
             break;
        case 1:
             //process string
             break;

         case 2:
             //process string
             break;
         case 3:
             //process string
             break;
         default:
             break;
      }
  }

This concept is still very new to me and I'm having hard time understanding its implementation. If anyone can shed some light, it'll be much appreciated.

What about drawing a diagram 1st? (https://en.wikipedia.org/wiki/Finite-state_machine) — alk, Jun 28 '15 at 14:21
Take a look at this my answer: http://stackoverflow.com/questions/1371460/state-machines-tutorials/1371654#1371654 — qrdl, Jun 28 '15 at 14:24
There's more than one way to do it. How comfortable are you with function pointers? — Beta, Jun 28 '15 at 14:26
Also "*`OCTAL`, `HEX`, `INTEGER`*": How the the latter compare to/differ from the former two? Did you probably mean `DECIMAL` instead of `INTEGER`? — alk, Jun 28 '15 at 14:27
Decide your input set first, and then draw a state diagram or a transition table. — Raman, Jun 28 '15 at 14:30
Also^2 you most likely need a state to start from, which would be which of the listed ones? — alk, Jun 28 '15 at 14:30
Nitpicking cont/: octals and hex numbers can be integers as well. — alk, Jun 28 '15 at 14:33
Ah yes, well I should change Integer to Decimal. I drew out the different states on paper, it's just its implementation that is confusing me. — Bret, Jun 28 '15 at 14:35
why do you think you need a state machine ? I wouldn't implement a state machine for this use case... see [the definition of a state machine](https://en.wikipedia.org/wiki/Finite-state_machine) — Ayman Khamouma, Jun 28 '15 at 14:37
As the code gets more complicated, like adding to check for floats, I can see my code becoming quite a long sequence of if-else statements. It gets the job done, but lacks efficiency. I want to try and implement a state machine design for both clarity and learning purposes. — Bret, Jun 28 '15 at 14:41
why floats are adding complexity ? they should no. you should have a list of valid chars for decimals. a list of valid chars for hex and a list of valid chars for octals. then check for the 1 or 2 first chars in order to detect the type, and confirm validity of the number by comparing the rest of the strig with the valid chars associated with the detected type. — Ayman Khamouma, Jun 28 '15 at 14:44
Possible duplicate of http://stackoverflow.com/questions/1647631/c-state-machine-design?rq=1 ? — Raman, Jun 28 '15 at 14:44
@AymanKhamouma: The task is parsing. Parsing can be implemented using a state-machine. — alk, Jun 28 '15 at 14:45
@alk yes it can. but for this use case does it really need a state machine ? allow me to doubt. but I guess this is personal point of view... — Ayman Khamouma, Jun 28 '15 at 14:48
Please do not change your question after answers/comments had been given. This might render such as ununderstandable. Add edits/updates as additions. — alk, Jun 28 '15 at 14:51
@Bret furthermore, you are confusing the result with the states... octal, hex, decimal should be the end-result of your state machine.not its states — Ayman Khamouma, Jun 28 '15 at 14:53
@Bret States should be seen as "atomic" actions that will help you process a complex task. — Ayman Khamouma, Jun 28 '15 at 14:54
Oh ok, so the states would be more like: FirstDigit, FirstTwoDigits (to check for hex) etc. — Bret, Jun 28 '15 at 14:55

Sumeet · Accepted Answer · 2015-06-29T04:48:08.357

It is a pretty much straight forward question and the solution is also very simple.

I have 7 states namely from 0 to 6 as shown by diagram.0 is the initial state. 3,4,5 could be the final states and 6 is the dead state.

enter image description here

state 0: Initial state and from this state we can only encounter following chars:

0 or O or 1-9

if any other char then an error is there and no need to process further.

state 1: if char from state 0 is 0 then this is the next state and

if char from this state is x then the string is hexadecimal(state=4) and no need to process further as any char can follow.

if char from this state is 0-7 then string is octal(state=5) and we process till the end of string to see if we get any char different from 0-7, if we do then error is there as invalid string and no need to process further as soon as we get it.

state 2: if char from state 0 is O then this is the next state and from this state if next char is X then string is hexadecimal(state=4) and no need to process further, if it is not then error is there.

state 3: if char from state 0 is 1-9 then string is decimal number(state=3) and we process till the end of string to see if we get any char different from 0-9, if we do then error is there as invalid string and no need to process further as soon as we get it.

state 4:hexadecimal number

state 5:octal number

state 6:error meaning invalid string

Here is the C code. I have taken the length of the string to be 9, just for simplicity and nothing else.

#include <stdio.h>
#include <stdlib.h>
int main()
{
  char *a="066676777";
  int state=0;int i=0;
  while(state!=6&&i<9)
  {
      switch(state)
      {
      case 0:
        if(a[i]=='0')
            state=1;
        else if(a[i]=='O')
            state=2;
        else if(a[i]>=49&&a[i]<=57)
            state=3;
        else {state=6;i=9;}
        break;
      case 1:
         if(a[i]=='x')
         {
              state=4;i=9;
         }
         else if(a[i]>=48&&a[i]<=55)
         {
             state=5;
             while(i<9)
                if(a[i]>=48&&a[i]<=55)
                 ++i;
                else {state=6;i=9;}
         }
         else {state=6;i=9;}
         break;
      case 2:
          if(a[i]=='X')
          {
              state=4;i=9;
          }
          else {state=6;i=9;}
         break;
      case 3:
          while(i<9)
            if(a[i]>=48&&a[i]<=57)
                ++i;
            else {state=6;i=9;}
            break;
      default:
        printf("please select correct initial state");
         break;
      }
      ++i;
    }
    if(state==3)
      printf("it is a decimal number");
    else if(state==4)
      printf("it is a hexadecimal number");
    else if(state==5)
      printf("it is a octal number");
    else printf("error encountered as invalid string");
}

Finite State Machine In C

1 Answers1

Linked