NFA to accept strings that has atleast one character occurring in a multiple of 3

0 0 17 minutes read

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 Q2
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
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
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
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
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
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
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
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
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
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;
    }
}
 
// Function to check for 3 b's
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;
    }
}
 
// Function to check for 3 c's
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;
    }
}
 
// Driver Code
int 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 Q2
def 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 Q3
def 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 Q4
def 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 Q5
def 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 Q6
def 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 Q7
def 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 Q8
def 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 Q9
def 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 Q10
def 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's
def 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's
def 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's
def 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 Code
 
s = "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 accepted
if (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 Q2
function 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 Q3
function 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 Q4
function 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 Q5
function 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 Q6
function 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 Q7
function 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 Q8
function 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 Q9
function 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 Q10
function 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's
function 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's
function 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's
function 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 Code
 
let 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 accepted
if (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 zambiatek!