C++ program to demonstrate Finite Automata

Hello everyone! In this tutorial, we are going to discuss Finite Automata in C++. An Automata can be also called as a computing device. An Automata is called a Finite Automata when it has a finite number of steps.

Sometimes, Finite Automata (FA) is also called as Finite State Machine (FSM).

To explain the concept of Finite Automata

A Finite Automata consists of five tuples {Q, ∑, q, F, δ}.

• Q:-  Consist set of Finite Non-empty set of states.
• δ:-  Transition or mapping function.
• ∑:-  Finite Non-empty set of inputs.
• q:-  initial state.
• F:-  Consist Set of final states.

 

Below is the code in C++ to demonstrate:

How to design an Automata that starts and ends with “b” where the inputs are {“a”, “b”}.

The below code will generate random strings with input states {a, b}, and checks whether it starts and ends with the same character or not.

 

// example of finite automata by Yaniv Jais
//to find a string starts and ends with b
#include <iostream> 
#include <time.h> 
#include <stdlib.h>
using namespace std; 
int generate_fxn(int maxi){
   int x = 0; 
    while (x < maxi) { 
        char word = 'a' + rand() % 2; //generate first word of string
        cout << word << " "; 
        x++; 
  
        // if the first character is 'b' 
        if (word == 'b') { 
            if (x == maxi) //checks if it has only one word then print yes
                cout << "YES\n"; 
  
            while (x < maxi) {  //else generate the full string 
                word = 'a' + rand() % 2; 
                cout << word << " "; 
                x++; 
  
                if (word == 'b' && x == maxi) { //if it is the last character and 'b'
                    cout << "\nYes, it satisfies the condition\n"; 
                } 
                else if (x == maxi) { 
                    cout << "\nNO\n"; 
                } 
            } 
        } 
  
        else { //if it does not start with 'b' then print NO
            while (x < maxi) { 
                word = 'a' + rand() % 2; 
                cout << word << " "; 
                x++; 
            } 
            cout << "\nNo, it doesn't satisfy the condition\n"; 
        } 
    } 
    return 0;
}
  
int main() 
{ 
    //srand is used to produce diffent random number each time you compile.
    srand(time(0)); 
  
    
    int maxi = 1 + rand() % 10; // we are generating random number from 1-10
  generate_fxn(maxi);
    return 0; 
}

Outputs:

Example 1:

b a b
Yes, it satisfies the condition

 

Example 2:

a b b a b
No, it doesn't satisfy the condition.

I hope I have cleared all your doubts regarding the topic.
Feel free to ask any queries in the comment section.

You may also visit:

• Generating pseudo-random numbers in C++
• Z algorithm in C++

Thank You.