Prerequisites: Finite Automata
Given a string str consisting of characters a, b and c, check if the number of occurrences of any character in the string is a multiple of 3 or not.
Examples:
Input: str = bc
Output: ACCEPTED
Explanation: The string consists 0 a’s and 3 * 0 = 0.Input: str = abccc
Output: ACCEPTED
Explanation: The string consists 3 c’s.Input: str = abc
Output: NOT ACCEPTED
Approach:
An NFA or a Nondeterministic Finite Automata is very similar to a DFA. It is a finite state machine that accepts a string(under some specific condition) if it reaches a final state, otherwise rejects it. The additional features which an NFA has are:
- Null move is allowed i.e., it can move forward without reading symbols.
- Ability to transmit to any number of states for a particular input.
NFA Machine that accepts all strings in which the occurrences of atleast one character is a multiple of 3:
For the above problem statement, we must first build an NFA machine. NFA machine is similar to a flowchart with various states and transitions. NFA machine corresponding to the above problem is shown below, Q3, Q4 and Q8 are the final states:
How does this NFA Machine work:
The working of the machine depends on checking if the string has 3 multiples of a’s or b’s or c’s.
- Case 1: Number of a’s is a multiple of three:
- To check whether the number of a’s in the string is a three multiple or not, a separate set of states is defined. The states defined as Q2, Q3, Q4 check whether the number of a’s is a multiple of three or not. If at any point this case reaches the final state Q2, then the number of a’s is a multiple of three.
- Case 2: Number of b’s is a multiple of three:
- To check whether the number of b’s in the string is a three multiple or not, a separate set of states is defined. The states defined as Q5, Q6, Q7 check whether the number of b’s is a multiple of three or not. If at any point this case reaches the final state Q5, then the number of b’s is a multiple of three.
- Case 3: Number of c’s is a multiple of three:
- To check whether the number of c’s in the string is a three multiple or not, a separate set of states is defined. The states defined as Q8, Q9, Q10 check whether the number of c’s is a multiple of three or not. If at any point this case reaches the final state Q8, then the number of c’s is a multiple of three.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>// NFA variable that keeps track of// the state while transaction.int nfa = 1;// This checks for invalid input.int flag = 0;using namespace std;// Function for the state Q2void state1(char c){ // State transitions // 'a' takes to Q4, and // 'b' and 'c' remain at Q2 if (c == 'a') nfa = 2; else if (c == 'b' || c == 'c') nfa = 1; else flag = 1;}// Function for the state Q3void state2(char c){ // State transitions // 'a' takes to Q3, and // 'b' and 'c' remain at Q4 if (c == 'a') nfa = 3; else if (c == 'b' || c == 'c') nfa = 2; else flag = 1;}// Function for the state Q4void state3(char c){ // State transitions // 'a' takes to Q2, and // 'b' and 'c' remain at Q3 if (c == 'a') nfa = 1; else if (c == 'b' || c == 'c') nfa = 3; else flag = 1;}// Function for the state Q5void state4(char c){ // State transitions // 'b' takes to Q6, and // 'a' and 'c' remain at Q5 if (c == 'b') nfa = 5; else if (c == 'a' || c == 'c') nfa = 4; else flag = 1;}// Function for the state Q6void state5(char c){ // State transitions // 'b' takes to Q7, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 6; else if (c == 'a' || c == 'c') nfa = 5; else flag = 1;}// Function for the state Q7void state6(char c){ // State transitions // 'b' takes to Q5, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 4; else if (c == 'a' || c == 'c') nfa = 6; else flag = 1;}// Function for the state Q8void state7(char c){ // State transitions // 'c' takes to Q9, and // 'a' and 'b' remain at Q8 if (c == 'c') nfa = 8; else if (c == 'b' || c == 'a') nfa = 7; else flag = 1;}// Function for the state Q9void state8(char c){ // State transitions // 'c' takes to Q10, and // 'a' and 'b' remain at Q9 if (c == 'c') nfa = 9; else if (c == 'b' || c == 'a') nfa = 8; else flag = 1;}// Function for the state Q10void state9(char c){ // State transitions // 'c' takes to Q8, and // 'a' and 'b' remain at Q10 if (c == 'c') nfa = 7; else if (c == 'b' || c == 'a') nfa = 9; else flag = 1;}// Function to check for 3 a'sbool checkA(string s, int x){ for (int i = 0; i < x; i++) { if (nfa == 1) state1(s[i]); else if (nfa == 2) state2(s[i]); else if (nfa == 3) state3(s[i]); } if (nfa == 1) { return true; } else { nfa = 4; }}// Function to check for 3 b'sbool checkB(string s, int x){ for (int i = 0; i < x; i++) { if (nfa == 4) state4(s[i]); else if (nfa == 5) state5(s[i]); else if (nfa == 6) state6(s[i]); } if (nfa == 4) { return true; } else { nfa = 7; }}// Function to check for 3 c'sbool checkC(string s, int x){ for (int i = 0; i < x; i++) { if (nfa == 7) state7(s[i]); else if (nfa == 8) state8(s[i]); else if (nfa == 9) state9(s[i]); } if (nfa == 7) { return true; }}// Driver Codeint main(){ string s = "bbbca"; int x = 5; // If any of the states is true, that is, if either // the number of a's or number of b's or number of c's // is a multiple of three, then the string is accepted if (checkA(s, x) || checkB(s, x) || checkC(s, x)) { cout << "ACCEPTED"; } else { if (flag == 0) { cout << "NOT ACCEPTED"; return 0; } else { cout << "INPUT OUT OF DICTIONARY."; return 0; } }} |
Java
// Java implementation of the above approach import java.io.*;public class GFG { // NFA variable that keeps track of // the state while transaction. static int nfa = 1; // This checks for invalid input. static int flag = 0; // Function for the state Q2 static void state1(char c) { // State transitions // 'a' takes to Q4, and // 'b' and 'c' remain at Q2 if (c == 'a') nfa = 2; else if (c == 'b' || c == 'c') nfa = 1; else flag = 1; } // Function for the state Q3 static void state2(char c) { // State transitions // 'a' takes to Q3, and // 'b' and 'c' remain at Q4 if (c == 'a') nfa = 3; else if (c == 'b' || c == 'c') nfa = 2; else flag = 1; } // Function for the state Q4 static void state3(char c) { // State transitions // 'a' takes to Q2, and // 'b' and 'c' remain at Q3 if (c == 'a') nfa = 1; else if (c == 'b' || c == 'c') nfa = 3; else flag = 1; } // Function for the state Q5 static void state4(char c) { // State transitions // 'b' takes to Q6, and // 'a' and 'c' remain at Q5 if (c == 'b') nfa = 5; else if (c == 'a' || c == 'c') nfa = 4; else flag = 1; } // Function for the state Q6 static void state5(char c) { // State transitions // 'b' takes to Q7, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 6; else if (c == 'a' || c == 'c') nfa = 5; else flag = 1; } // Function for the state Q7 static void state6(char c) { // State transitions // 'b' takes to Q5, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 4; else if (c == 'a' || c == 'c') nfa = 6; else flag = 1; } // Function for the state Q8 static void state7(char c) { // State transitions // 'c' takes to Q9, and // 'a' and 'b' remain at Q8 if (c == 'c') nfa = 8; else if (c == 'b' || c == 'a') nfa = 7; else flag = 1; } // Function for the state Q9 static void state8(char c) { // State transitions // 'c' takes to Q10, and // 'a' and 'b' remain at Q9 if (c == 'c') nfa = 9; else if (c == 'b' || c == 'a') nfa = 8; else flag = 1; } // Function for the state Q10 static void state9(char c) { // State transitions // 'c' takes to Q8, and // 'a' and 'b' remain at Q10 if (c == 'c') nfa = 7; else if (c == 'b' || c == 'a') nfa = 9; else flag = 1; } // Function to check for 3 a's static boolean checkA(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 1) state1(s.charAt(i)); else if (nfa == 2) state2(s.charAt(i)); else if (nfa == 3) state3(s.charAt(i)); } if (nfa == 1) { return true; } else { nfa = 4; } return false;} // Function to check for 3 b's static boolean checkB(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 4) state4(s.charAt(i)); else if (nfa == 5) state5(s.charAt(i)); else if (nfa == 6) state6(s.charAt(i)); } if (nfa == 4) { return true; } else { nfa = 7; } return false;} // Function to check for 3 c's static boolean checkC(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 7) state7(s.charAt(i)); else if (nfa == 8) state8(s.charAt(i)); else if (nfa == 9) state9(s.charAt(i)); } if (nfa == 7) { return true; } return false;} // Driver Code public static void main (String[] args){ String s = "bbbca"; int x = 5; // If any of the states is true, that is, if either // the number of a's or number of b's or number of c's // is a multiple of three, then the string is accepted if (checkA(s, x) || checkB(s, x) || checkC(s, x)) { System.out.println("ACCEPTED"); } else { if (flag == 0) { System.out.println("NOT ACCEPTED"); } else { System.out.println("INPUT OUT OF DICTIONARY."); } } } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the above approach# NFA variable that keeps track of# the state while transaction.nfa = 1# This checks for invalid input.flag = 0# Function for the state Q2def state1(c): global nfa,flag # State transitions # 'a' takes to Q4, and # 'b' and 'c' remain at Q2 if (c == 'a'): nfa = 2 elif (c == 'b' or c == 'c'): nfa = 1 else: flag = 1# Function for the state Q3def state2(c): global nfa,flag # State transitions # 'a' takes to Q3, and # 'b' and 'c' remain at Q4 if (c == 'a'): nfa = 3 elif (c == 'b' or c == 'c'): nfa = 2 else: flag = 1# Function for the state Q4def state3(c): global nfa,flag # State transitions # 'a' takes to Q2, and # 'b' and 'c' remain at Q3 if (c == 'a'): nfa = 1 elif (c == 'b' or c == 'c'): nfa = 3 else: flag = 1# Function for the state Q5def state4(c): global nfa,flag # State transitions # 'b' takes to Q6, and # 'a' and 'c' remain at Q5 if (c == 'b'): nfa = 5 elif (c == 'a' or c == 'c'): nfa = 4 else: flag = 1# Function for the state Q6def state5(c): global nfa, flag # State transitions # 'b' takes to Q7, and # 'a' and 'c' remain at Q7 if (c == 'b'): nfa = 6 elif (c == 'a' or c == 'c'): nfa = 5 else: flag = 1# Function for the state Q7def state6(c): global nfa,flag # State transitions # 'b' takes to Q5, and # 'a' and 'c' remain at Q7 if (c == 'b'): nfa = 4 elif (c == 'a' or c == 'c'): nfa = 6 else: flag = 1# Function for the state Q8def state7(c): global nfa,flag # State transitions # 'c' takes to Q9, and # 'a' and 'b' remain at Q8 if (c == 'c'): nfa = 8 elif (c == 'b' or c == 'a'): nfa = 7 else: flag = 1# Function for the state Q9def state8(c): global nfa,flag # State transitions # 'c' takes to Q10, and # 'a' and 'b' remain at Q9 if (c == 'c'): nfa = 9 elif (c == 'b' or c == 'a'): nfa = 8 else: flag = 1# Function for the state Q10def state9(c): global nfa,flag # State transitions # 'c' takes to Q8, and # 'a' and 'b' remain at Q10 if (c == 'c'): nfa = 7 elif (c == 'b' or c == 'a'): nfa = 9 else: flag = 1 # Function to check for 3 a'sdef checkA(s, x): global nfa,flag for i in range(x): if (nfa == 1): state1(s[i]) elif (nfa == 2): state2(s[i]) elif (nfa == 3): state3(s[i]) if (nfa == 1): return True else: nfa = 4 # Function to check for 3 b'sdef checkB(s, x): global nfa,flag for i in range(x): if (nfa == 4): state4(s[i]) elif (nfa == 5): state5(s[i]) elif (nfa == 6): state6(s[i]) if (nfa == 4): return True else: nfa = 7 # Function to check for 3 c'sdef checkC(s, x): global nfa, flag for i in range(x): if (nfa == 7): state7(s[i]) elif (nfa == 8): state8(s[i]) elif (nfa == 9): state9(s[i]) if (nfa == 7): return True# Driver Codes = "bbbca"x = 5# If any of the states is True, that is, if either# the number of a's or number of b's or number of c's# is a multiple of three, then the is acceptedif (checkA(s, x) or checkB(s, x) or checkC(s, x)): print("ACCEPTED")else: if (flag == 0): print("NOT ACCEPTED") else: print("INPUT OUT OF DICTIONARY.") # This code is contributed by shubhamsingh10 |
C#
// C# implementation of the above approach using System;class GFG { // NFA variable that keeps track of // the state while transaction. static int nfa = 1; // This checks for invalid input. static int flag = 0; // Function for the state Q2 static void state1(char c) { // State transitions // 'a' takes to Q4, and // 'b' and 'c' remain at Q2 if (c == 'a') nfa = 2; else if (c == 'b' || c == 'c') nfa = 1; else flag = 1; } // Function for the state Q3 static void state2(char c) { // State transitions // 'a' takes to Q3, and // 'b' and 'c' remain at Q4 if (c == 'a') nfa = 3; else if (c == 'b' || c == 'c') nfa = 2; else flag = 1; } // Function for the state Q4 static void state3(char c) { // State transitions // 'a' takes to Q2, and // 'b' and 'c' remain at Q3 if (c == 'a') nfa = 1; else if (c == 'b' || c == 'c') nfa = 3; else flag = 1; } // Function for the state Q5 static void state4(char c) { // State transitions // 'b' takes to Q6, and // 'a' and 'c' remain at Q5 if (c == 'b') nfa = 5; else if (c == 'a' || c == 'c') nfa = 4; else flag = 1; } // Function for the state Q6 static void state5(char c) { // State transitions // 'b' takes to Q7, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 6; else if (c == 'a' || c == 'c') nfa = 5; else flag = 1; } // Function for the state Q7 static void state6(char c) { // State transitions // 'b' takes to Q5, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 4; else if (c == 'a' || c == 'c') nfa = 6; else flag = 1; } // Function for the state Q8 static void state7(char c) { // State transitions // 'c' takes to Q9, and // 'a' and 'b' remain at Q8 if (c == 'c') nfa = 8; else if (c == 'b' || c == 'a') nfa = 7; else flag = 1; } // Function for the state Q9 static void state8(char c) { // State transitions // 'c' takes to Q10, and // 'a' and 'b' remain at Q9 if (c == 'c') nfa = 9; else if (c == 'b' || c == 'a') nfa = 8; else flag = 1; } // Function for the state Q10 static void state9(char c) { // State transitions // 'c' takes to Q8, and // 'a' and 'b' remain at Q10 if (c == 'c') nfa = 7; else if (c == 'b' || c == 'a') nfa = 9; else flag = 1; } // Function to check for 3 a's static bool checkA(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 1) state1(s[i]); else if (nfa == 2) state2(s[i]); else if (nfa == 3) state3(s[i]); } if (nfa == 1) { return true; } else { nfa = 4; } return false;} // Function to check for 3 b's static bool checkB(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 4) state4(s[i]); else if (nfa == 5) state5(s[i]); else if (nfa == 6) state6(s[i]); } if (nfa == 4) { return true; } else { nfa = 7; } return false;} // Function to check for 3 c's static bool checkC(String s, int x) { for (int i = 0; i < x; i++) { if (nfa == 7) state7(s[i]); else if (nfa == 8) state8(s[i]); else if (nfa == 9) state9(s[i]); } if (nfa == 7) { return true; } return false;} // Driver Code public static void Main(String[] args){ String s = "bbbca"; int x = 5; // If any of the states is true, that is, if either // the number of a's or number of b's or number of c's // is a multiple of three, then the string is accepted if (checkA(s, x) || checkB(s, x) || checkC(s, x)) { Console.WriteLine("ACCEPTED"); } else { if (flag == 0) { Console.WriteLine("NOT ACCEPTED"); } else { Console.WriteLine("INPUT OUT OF DICTIONARY."); } } } }// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the above approach// NFA variable that keeps track of// the state while transaction.let nfa = 1;// This checks for invalid input.let flag = 0;// Function for the state Q2function state1(c) { // State transitions // 'a' takes to Q4, and // 'b' and 'c' remain at Q2 if (c == 'a') nfa = 2; else if (c == 'b' || c == 'c') nfa = 1; else flag = 1;}// Function for the state Q3function state2(c) { // State transitions // 'a' takes to Q3, and // 'b' and 'c' remain at Q4 if (c == 'a') nfa = 3; else if (c == 'b' || c == 'c') nfa = 2; else flag = 1;}// Function for the state Q4function state3(c) { // State transitions // 'a' takes to Q2, and // 'b' and 'c' remain at Q3 if (c == 'a') nfa = 1; else if (c == 'b' || c == 'c') nfa = 3; else flag = 1;}// Function for the state Q5function state4(c) { // State transitions // 'b' takes to Q6, and // 'a' and 'c' remain at Q5 if (c == 'b') nfa = 5; else if (c == 'a' || c == 'c') nfa = 4; else flag = 1;}// Function for the state Q6function state5(c) { // State transitions // 'b' takes to Q7, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 6; else if (c == 'a' || c == 'c') nfa = 5; else flag = 1;}// Function for the state Q7function state6(c) { // State transitions // 'b' takes to Q5, and // 'a' and 'c' remain at Q7 if (c == 'b') nfa = 4; else if (c == 'a' || c == 'c') nfa = 6; else flag = 1;}// Function for the state Q8function state7(c) { // State transitions // 'c' takes to Q9, and // 'a' and 'b' remain at Q8 if (c == 'c') nfa = 8; else if (c == 'b' || c == 'a') nfa = 7; else flag = 1;}// Function for the state Q9function state8(c) { // State transitions // 'c' takes to Q10, and // 'a' and 'b' remain at Q9 if (c == 'c') nfa = 9; else if (c == 'b' || c == 'a') nfa = 8; else flag = 1;}// Function for the state Q10function state9(c) { // State transitions // 'c' takes to Q8, and // 'a' and 'b' remain at Q10 if (c == 'c') nfa = 7; else if (c == 'b' || c == 'a') nfa = 9; else flag = 1;}// Function to check for 3 a'sfunction checkA(s, x) { for (let i = 0; i < x; i++) { if (nfa == 1) state1(s[i]); else if (nfa == 2) state2(s[i]); else if (nfa == 3) state3(s[i]); } if (nfa == 1) { return true; } else { nfa = 4; }}// Function to check for 3 b'sfunction checkB(s, x) { for (let i = 0; i < x; i++) { if (nfa == 4) state4(s[i]); else if (nfa == 5) state5(s[i]); else if (nfa == 6) state6(s[i]); } if (nfa == 4) { return true; } else { nfa = 7; }}// Function to check for 3 c'sfunction checkC(s, x) { for (let i = 0; i < x; i++) { if (nfa == 7) state7(s[i]); else if (nfa == 8) state8(s[i]); else if (nfa == 9) state9(s[i]); } if (nfa == 7) { return true; }}// Driver Codelet s = "bbbca";let x = 5;// If any of the states is true, that is, if either// the number of a's or number of b's or number of c's// is a multiple of three, then the string is acceptedif (checkA(s, x) || checkB(s, x) || checkC(s, x)) { document.write("ACCEPTED");}else { if (flag == 0) { document.write("NOT ACCEPTED"); } else { document.write("INPUT OUT OF DICTIONARY."); }}// This code is contributed by gfgking</script> |
Output:
ACCEPTED
Time Complexity: O(x)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
