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:
Thank You.
Thank you so much Vivek kumar Jaiswal. It really helped me a lot, now my doubts are cleared. Keep posting more such codes