NFA para aceptar strings que tienen al menos un carácter que ocurre en un múltiplo de 3

Prerrequisitos: Autómatas finitos
Dada una string str que consta de los caracteres a , b y c , verifique si el número de ocurrencias de cualquier carácter en la string es un múltiplo de 3 o no. 

Ejemplos: 

Entrada: str = bc 
Salida: ACEPTADO 
Explicación: La string consta de 0 a y 3 * 0 = 0.

Entrada: str = abccc 
Salida: ACEPTADO 
Explicación: La string consta de 3 c. 

Entrada: str = abc 
Salida: NO ACEPTADO 
 

Enfoque: 
un NFA o un autómata finito no determinista es muy similar a un DFA . Es una máquina de estados finitos que acepta una string (bajo alguna condición específica) si alcanza un estado final, de lo contrario la rechaza. Las características adicionales que tiene un NFA son: 

1. Se permite el movimiento nulo, es decir, puede avanzar sin leer símbolos.
2. Capacidad de transmitir a cualquier número de estados para una entrada en particular.

Máquina NFA que acepta todas las strings en las que la aparición de al menos un carácter es un múltiplo de 3 : 
Para la declaración del problema anterior, primero debemos construir una máquina NFA. La máquina NFA es similar a un diagrama de flujo con varios estados y transiciones. La máquina NFA correspondiente al problema anterior se muestra a continuación, Q3, Q4 y Q8 son los estados finales:
 

Cómo funciona esta máquina NFA: 
El funcionamiento de la máquina depende de verificar si la string tiene 3 múltiplos de a, b o c. 

• Caso 1: El número de a es un múltiplo de tres:
  • Para verificar si el número de a en la string es un múltiplo de tres o no, se define un conjunto separado de estados. Los estados definidos como Q2, Q3, Q4 comprueban si el número de a es múltiplo de tres o no. Si en algún momento este caso alcanza el estado final Q2, entonces el número de a es un múltiplo de tres.
• Caso 2: El número de b es un múltiplo de tres:
  • Para verificar si el número de b en la string es un múltiplo de tres o no, se define un conjunto separado de estados. Los estados definidos como Q5, Q6, Q7 comprueban si el número de b es múltiplo de tres o no. Si en algún momento este caso llega al estado final Q5, entonces el número de b es un múltiplo de tres.
• Caso 3: El número de c es un múltiplo de tres:
  • Para verificar si el número de c en la string es un múltiplo de tres o no, se define un conjunto separado de estados. Los estados definidos como Q8, Q9, Q10 comprueban si el número de c es múltiplo de tres o no. Si en algún momento este caso llega al estado final Q8, entonces el número de c es un múltiplo de tres.

A continuación se muestra la implementación del enfoque anterior:  

// 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 implementation of the above approach
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 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# 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

<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>

ACCEPTED

Complejidad del Tiempo: O(x)

Espacio Auxiliar: O(1)