DFA que reconoce que el número 0 es múltiplo de 3 en la entrada {0,1}

Finite Automata se conoce como una máquina de estados finitos que son aceptables, de lo contrario no son aceptables. en el alfabeto de entrada ‘0’ y 1′.

  • Determinar el estado inicial.
  • La transición ocurre en cada alfabeto de entrada.
  • Determine si el bucle automático debe aplicarse o no.
  • El estado final de Mark.

Diseño de DFA paso a paso:
Paso 1: 
haga que el estado inicial sea «A», entonces existe la posibilidad de que no haya ningún ‘0’ pero solo tenga ‘1’ en la string, lo cual es aceptable porque 0 es divisible por 3. Entonces , en este caso, ningún número de 1 puede estar presente aquí y para esto coloque el bucle automático de ‘1’ en el estado inicial «A».

Paso 2: 
Cree la transición del alfabeto de entrada ‘0’ del estado «A» al estado «B».
 

Paso 3: 
Después de un ‘0’, cualquier número de 1 puede estar presente, es decir, ningún ‘1’ o más de un ‘1’. Para esto, coloque el bucle de ‘1’ en el estado «B».
 

Paso 4: 
Ahora cree la transición del alfabeto de entrada ‘0’ del estado «B» al estado «C» y después de dos 0 se puede encontrar cualquier número de 1 en la string y para esto coloque el bucle automático de ‘1’ en el estado inicial «C».
 

Paso 5: 
antes de la transición del tercer ‘0’, debemos pensar en la lógica para que, después de esta transición, la máquina acepte una string que tenga un número de ceros divisible por 3. Para este tránsito ‘o’ del estado «C» al estado “A”. Como el tercer cero está llegando al estado “A”, entonces haga que el estado “A” sea el estado final.
 

Tabla de transición de DFA anterior:

estados Entrada (0) Entrada (1)
—> Un * B A
B C B
C A C

En la tabla anterior, —> representa el estado inicial y * representa el estado final. En este artículo, el estado inicial y final es el mismo que es el estado final.
Reglas de transición de DFA anterior: 

Implementar : 

Java

// Java code for the above DFA
import java.util.*;
 
class GFG{
      
// Function for the state A
static void checkStateA(String n)
{
     
    // Check length of n
    // is 0 then print
    // String accepted
    if (n.length() == 0)
        System.out.print("String accepted");
     
    // If 1 is found call function
    // checkStateA otherwise if 0
    // is found call function stateB
    else
    {
        if (n.charAt(0) == '1')
            checkStateA(n.substring(1));
        else
            stateB(n.substring(1));
    }
}
   
// Function for the state B
static void stateB(String n)
{
     
    // Check length of n
    // is 0 then print
    // String not accepted
    if (n.length() == 0)
        System.out.print("String not accepted");
     
    // If 1 is found call function
    // stateB otherwise if 0
    // is found call function stateC   
    else
    {
        if (n.charAt(0) == '1')
            stateB(n.substring(1));
        else
            stateC(n.substring(1));
    }
}
  
// Function for the state C
static void stateC(String n)
{
     
    // Check length of n
    // is 0 then print
    // String not accepted
    if (n.length() == 0)
        System.out.print("String not accepted");
     
    // If 1 is found call function
    // stateC otherwise if 0
    // is found call function checkStateA
    else
    {
        if (n.charAt(0) == '1')
            stateC(n.substring(1));
        else
            checkStateA(n.substring(1));
    }
}
  
// Driver code
public static void main(String []args)
{
    Scanner sc = new Scanner(System.in);
     
    // Take String input
    String n = sc.nextLine();
     
    // Call checkStateA to
    // check the inputted String
    checkStateA(n);
}
}
 
// This code is contributed by pratham76

Python3

# Python3 code for the above DFA
def checkStateA(n):
     
    # check length of n
    # is 0 then print
    # string accepted
    if(len(n)== 0):
        print("string accepted")
         
    # if 1 is found call function
    # checkStateA otherwise if 0
    # is found call function stateB
    else:   
        if(n[0]=='1'):
            checkStateA(n[1:])
        else:
            stateB(n[1:])
  
  
def stateB(n):
     
    # check length of n
    # is 0 then print
    # string not accepted
    if(len(n)== 0):
        print("string not accepted")
         
    # if 1 is found call function
    # stateB otherwise if 0
    # is found call function stateC   
    else:   
        if(n[0]=='1'):
            stateB(n[1:])
        else:
            stateC(n[1:])
        
         
def stateC(n):
     
    # check length of n
    # is 0 then print
    # string not accepted
    if(len(n)== 0):
        print("string not accepted")
         
    # if 1 is found call function
    # stateC otherwise if 0
    # is found call function checkStateA
    else:   
        if(n[0]=='1'):
            stateC(n[1:])
        else:
            checkStateA(n[1:])
         
# take string input
n = input()
 
# call checkStateA
# to check the inputted string
checkStateA(n)

C#

// C# code for the above DFA
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
     
// Function for the state A
static void checkStateA(string n)
{
  // check length of n
  // is 0 then print
  // string accepted
  if(n.Length == 0)
    Console.Write("string accepted");
 
  // if 1 is found call function
  // checkStateA otherwise if 0
  // is found call function stateB
  else
  {
    if(n[0] == '1')
      checkStateA(n.Substring(1));
    else
      stateB(n.Substring(1));
  }
}
  
// Function for the state B
static void stateB(string n)
{
  // check length of n
  // is 0 then print
  // string not accepted
  if(n.Length == 0)
    Console.Write("string not accepted");
 
  // if 1 is found call function
  // stateB otherwise if 0
  // is found call function stateC   
  else{
    if(n[0] == '1')
      stateB(n.Substring(1));
    else
      stateC(n.Substring(1));
  }
}
 
// Function for the state C
static void stateC(string n)
{
  // check length of n
  // is 0 then print
  // string not accepted
  if(n.Length == 0)
    Console.Write("string not accepted");
 
  // if 1 is found call function
  // stateC otherwise if 0
  // is found call function checkStateA
  else
  {
    if(n[0] == '1')
      stateC(n.Substring(1));
    else
      checkStateA(n.Substring(1));
  }
}
 
// Driver code
public static void Main(string []args)
{
  // take string input
  string n = Console.ReadLine();
 
  // call checkStateA
  // to check the inputted string
  checkStateA(n);
}
}
 
// This code is contributed by rutvik_56

Publicación traducida automáticamente

Artículo escrito por _mridul_bhardwaj_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *