example-state-machine.c

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

// Define the states as constants
#define Q0 0
#define Q1 1

// Define the alphabet as an array of characters
char alphabet[] = {'0', '1'};

// Define the transition function as a 2D array of integers
int transition[][2] = {{Q0, Q1}, {Q0, Q1}};

// Define the initial state as an integer
int initial = Q0;

// Define the final state as an integer
int final = Q1;

// Define a function that checks if a character is in the alphabet
int is_in_alphabet(char c) {
  for (int i = 0; i < sizeof(alphabet); i++) {
    if (c == alphabet[i]) {
      return 1;
    }
  }
  return 0;
}

// Define a function that runs the state machine on a given input string
int run_state_machine(char* input) {
  // Initialize the current state to the initial state
  int current = initial;
  // Loop through each character of the input string
  for (int i = 0; i < strlen(input); i++) {
    // Check if the character is in the alphabet
    if (is_in_alphabet(input[i])) {
      // Get the index of the character in the alphabet
      int index = input[i] - '0'; // do not understand how this works  in c?
      // Update the current state using the transition function
      current = transition[current][index];
    } else {
      // Reject the input if the character is not in the alphabet
      return 0;
    }
  }
  // Check if the current state is the final state
  if (current == final) {
    // Accept the input if the current state is the final state
    return 1;
  } else {
    // Reject the input if the current state is not the final state
    return 0;
  }
}

// Define a function that tests the state machine on some examples
void test_state_machine() {
  // Define some example input strings
  char* examples[] = {"0", "1", "01", "10", "11", "101", "110", "111", "1001", "1010", "1101", "1110", "1111", "0000", "0101", "0011", "0110", "0001", "0010", "0100", "1000", "2", "12", "21", "a", "b", ""};
  // Loop through each example input string
  for (int i = 0; i < sizeof(examples) / sizeof(char*); i++) {
    // Run the state machine on the example input string
    int result = run_state_machine(examples[i]);
    // Print the result
    printf("Input: %s, Output: %s\n", examples[i], result ? "Accepted" : "Rejected");
  }
}

// Define the main function
int main() {
  // Test the state machine
  test_state_machine();
  // Exit the program
  return 0;
}