Cree un DFA para aceptar strings binarias que comiencen o terminen con «01»

Dada la string binaria str , la tarea es crear un DFA que acepte la string si la string comienza con «01» o termina con «01». 

Entrada: str = “010000” 
Salida: Aceptada 
Explicación: 
La string dada comienza con “01”.

Entrada: str = “1100111” 
Salida: No aceptado 
Explicación: 
La string dada no comienza ni termina con “01”. 

DFA o Deterministic Finite Automata 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.
En DFA, no existe el concepto de memoria, por lo tanto, debemos verificar la string carácter por carácter, comenzando con el carácter 0. El conjunto de caracteres de entrada para el problema es {0, 1}. Para que un DFA sea válido, debe haber una regla de transición definida para cada símbolo del conjunto de entrada en cada estado a un estado válido. Por lo tanto, se siguen los siguientes pasos para diseñar el DFA:

• En este caso, las strings que comienzan con 01 o terminan con 01 o ambas comienzan con 01 y terminan con 01 deberían ser aceptables.
• Haga un estado inicial y transite sus alfabetos de entrada, es decir, 0 y 1 a dos estados diferentes.
• Verifique la aceptación de la string después de cada transición para ignorar los errores.
• Primero, haga DfA para una string de longitud mínima y luego avance paso a paso.
• Defina los estados finales de acuerdo con la aceptación de la string.

Enfoque paso a paso para diseñar un DFA: 

• Paso 1: Hacer un estado inicial «A». La string mínima posible es 01, que es aceptable. Para esto, haga la transición de 0 del estado “A” al estado “B” y luego haga la transición de 1 del estado “B” al estado “C” y observe este estado “C” como el estado final.

• Paso 2: ahora, hemos diseñado el DFA que comienza con 01. Para aceptar todas las strings que comienzan con 01 como 011, 010, 010000, 01111, 010101000010001, etc., necesitamos poner un bucle automático de 0 y 1 en el estado “C”. Este bucle automático contiene todas las combinaciones de 0 y 1.

• Paso 3: Ahora, debemos pensar en la string que termina con «01». Hemos hecho la transición de 0 del estado «A», luego con la entrada 1 del estado «A». Con esta mínima string posible que termina en 01 es 101. Para esto, haga la transición de la entrada 1 del estado “A” al estado “D” luego haga la transición de la entrada 0 del estado “D” al estado “E” y luego haga la transición de la entrada 1 del estado «E» al estado «F» y observe este estado «F» como el estado final.

• Paso 4: Hay una posibilidad más de que cualquier número de 1 comience y luego termine con 01. Para esto, haga un bucle automático de 1 en el estado «D» y cualquier número de ceros puede venir antes del 1 que viene en el final. Para esto, ponga un bucle automático de 0 y el estado «E».

• Paso 5: Hasta ahora hemos terminado con las strings que comienzan con 1 y terminan con 01. Ahora, necesitamos pensar en la string que comienza con 0 y termina con 01. Para esto, haga una transición de entrada 0 desde el estado “ B” al estado “E”.

• Paso 6: Ahora solo nos quedan los alfabetos de entrada del estado “F”. Transite la entrada 1 del estado «F» al estado «D» y luego haga transitar la entrada 0 del estado «F» al estado «E».

Tabla de transición y reglas de transición del DFA anterior:

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

// C++ program to check if a string
// either starts or ends with 01
#include<bits/stdc++.h>
using namespace std;
 
void stateA(string);
void stateB(string);
void stateC(string);
void stateD(string);
void stateE(string);
void stateF(string);
 
// Function for transition
// state A
void checkstateA(string n)
{
     
    // State transition to
    // B if the character is
    // 0
    if(n[0] == '0')
       stateB(n.substr(1));
        
    // State transition to
    // D if the character is
    // 1
    else
       stateD(n.substr(1));
}
 
// Function for transition
// state B        
void stateB(string n)
{
     
    // Check if the string has
    // ended
    if (n.length() == 0)
        cout << "string not accepted";
    else
    {
         
        // State transition to C
        // if the character is 1
        if(n[0] == '1')
            stateC(n.substr(1));
 
        // State transition to D
        // if the character is 0
        else
            stateD(n.substr(1));
    }    
}
 
// Function for transition
// state C
void stateC(string n)
{
    cout << "String accepted";
}
 
// Function for transition
// state D
void stateD(string n)
{
    if (n.length() == 0)
        cout << "string not accepted";
    else
    {
         
        // State transition to D
        // if the character is 1
        if (n[0] == '1')
            stateD(n.substr(1));
 
        // State transition to E
        // if the character is 0
        else
            stateE(n.substr(1));
    }
}
 
// Function for transition
// state E
void stateE(string n)
{
    if (n.length() == 0)
        cout << "string not accepted";
    else
    {
         
        // State transition to E
        // if the character is 0
        if(n[0] == '0')
            stateE(n.substr(1));
 
        // State transition to F
        // if the character is 1
        else
            stateF(n.substr(1));
    }
}
 
// Function for transition
// state F
void stateF(string n)
{
    if(n.length() == 0)
        cout << "string accepred";
    else
    {
         
        // State transition to D
        // if the character is 1
        if(n[0] == '1')
            stateD(n.substr(1));
 
        // State transition to E
        // if the character is 0
        else
            stateE(n.substr(1));
    }
}
 
// Driver code
int main()
{
    string n = "0100101";
     
    checkstateA(n);
    return 0;
}
 
// This code is contributed by chitranayal

// Java program to check if a string
// either starts or ends with 01
import java.util.*;
 
class GFG{
     
// Function for transition
// state A
static void checkstateA(String n)
{
     
    // State transition to
    // B if the character is
    // 0
    if (n.charAt(0) == '0')
       stateB(n.substring(1));
        
    // State transition to
    // D if the character is
    // 1
    else
       stateD(n.substring(1));
}
 
// Function for transition
// state B        
static void stateB(String n)
{
     
    // Check if the string has
    // ended
    if (n.length() == 0)
        System.out.println("string not accepted");
    else
    {
         
        // State transition to C
        // if the character is 1
        if (n.charAt(0) == '1')
            stateC(n.substring(1));
 
        // State transition to D
        // if the character is 0
        else
            stateD(n.substring(1));
    }    
}
 
// Function for transition
// state C
static void stateC(String n)
{
    System.out.println("String accepted");
}
 
// Function for transition
// state D
static void stateD(String n)
{
    if (n.length() == 0)
        System.out.println("string not accepted");
    else
    {
         
        // State transition to D
        // if the character is 1
        if (n.charAt(0) == '1')
            stateD(n.substring(1));
 
        // State transition to E
        // if the character is 0
        else
            stateE(n.substring(1));
    }
}
 
// Function for transition
// state E
static void stateE(String n)
{
    if (n.length() == 0)
       System.out.println("string not accepted");
    else
    {
         
        // State transition to E
        // if the character is 0
        if(n.charAt(0) == '0')
            stateE(n.substring(1));
 
        // State transition to F
        // if the character is 1
        else
            stateF(n.substring(1));
    }
}
 
// Function for transition
// state F
static void stateF(String n)
{
    if (n.length() == 0)
        System.out.println("string accepred");
    else
    {
         
        // State transition to D
        // if the character is 1
        if (n.charAt(0) == '1')
            stateD(n.substring(1));
 
        // State transition to E
        // if the character is 0
        else
            stateE(n.substring(1));
    }
}
 
// Driver Code
public static void main(String args[])
{
    String n = "0100101";
     
    checkstateA(n);
}
}
 
// This code is contributed by jyoti369

# Python3 program to check if
# a string either starts or
# ends with 01
 
# Function for transition
# state A
def checkstateA(n):
 
    # State transition to
    # B if the character is
    # 0
    if(n[0]=='0'):
        stateB(n[1:])
 
    # State transition to
    # D if the character is
    # 1
    else:
        stateD(n[1:])
 
# Function for transition
# state B        
def stateB(n):
 
    # Check if the string has
    # ended
    if (len(n)== 0):
        print("string not accepted")
    else:   
     
        # State transition to C
        # if the character is 1
        if(n[0]=='1'):
            stateC(n[1:])
 
        # State transition to D
        # if the character is 0
        else:
            stateD(n[1:])
          
# Function for transition
# state C   
def stateC(n):
    print("String accepted")
  
# Function for transition
# state D
def stateD(n):
    if (len(n)== 0):
        print("string not accepted")
    else:   
 
        # State transition to D
        # if the character is 1
        if (n[0]=='1'):
            stateD(n[1:])
 
        # State transition to E
        # if the character is 0
        else:
            stateE(n[1:])
  
# Function for transition
# state E
def stateE(n):
    if (len(n)== 0):
        print("string not accepted")
    else:  
 
        # State transition to E
        # if the character is 0
        if(n[0]=='0'):
            stateE(n[1:])
 
        # State transition to F
        # if the character is 1
        else:
            stateF(n[1:])
  
# Function for transition
# state F
def stateF(n):
    if(len(n)== 0):
        print("string accepred")
    else:
 
        # State transition to D
        # if the character is 1
        if(n[0]=='1'):
            stateD(n[1:])
 
        # State transition to E
        # if the character is 0
        else:
            stateE(n[1:])
      
# Driver code
if __name__ == "__main__":
    n = "0100101"
    checkstateA(n)

// C# program to check if
// a string either starts
// or ends with 01
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
     
// Function for transition
// state A
static void checkstateA(string n)
{
  // State transition to
  // B if the character is
  // 0
  if(n[0] == '0')
    stateB(n.Substring(1));
 
  // State transition to
  // D if the character is
  // 1
  else
    stateD(n.Substring(1));
}
  
// Function for transition
// state B        
static void stateB(string n)
{    
  // Check if the string has
  // ended
  if (n.Length == 0)
  {
    Console.Write("string not accepted");
  }
  else
  {
    // State transition to C
    // if the character is 1
    if(n[0] == '1')
      stateC(n.Substring(1));
 
    // State transition to D
    // if the character is 0
    else
      stateD(n.Substring(1));
  }    
}
 
// Function for transition
// state C
static void stateC(string n)
{
  Console.Write("string accepted");
}
  
// Function for transition
// state D
static void stateD(string n)
{
  if (n.Length == 0)
    Console.Write("string not accepted");
  else
  {
 
    // State transition to D
    // if the character is 1
    if (n[0] == '1')
      stateD(n.Substring(1));
 
    // State transition to E
    // if the character is 0
    else
      stateE(n.Substring(1));
  }
}
  
// Function for transition
// state E
static void stateE(string n)
{
  if (n.Length == 0)
    Console.Write("string not accepted");
  else
  {
 
    // State transition to E
    // if the character is 0
    if(n[0] == '0')
      stateE(n.Substring(1));
 
    // State transition to F
    // if the character is 1
    else
      stateF(n.Substring(1));
  }
}
  
// Function for transition
// state F
static void stateF(string n)
{
  if(n.Length == 0)
    Console.Write("string accepted");
  else
  {
    // State transition to D
    // if the character is 1
    if(n[0] == '1')
      stateD(n.Substring(1));
 
    // State transition to E
    // if the character is 0
    else
      stateE(n.Substring(1));
  }
}
 
// Driver code
public static void Main(string []args)
{
  string n = "0100101";
  checkstateA(n);
}
}
 
// This code is contributed by rutvik_56

<script>
 
// JavaScript program to check if
// a string either starts
// or ends with 01
 
// Function for transition
// state A
function checkstateA(n)
{
  // State transition to
  // B if the character is
  // 0
  if(n[0] == '0')
    stateB(n.substr(1));
  
  // State transition to
  // D if the character is
  // 1
  else
    stateD(n.substr(1));
}
   
// Function for transition
// state B       
function stateB(n)
{   
  // Check if the string has
  // ended
  if (n.length == 0)
  {
    document.write("string not accepted");
  }
  else
  {
    // State transition to C
    // if the character is 1
    if(n[0] == '1')
      stateC(n.substr(1));
  
    // State transition to D
    // if the character is 0
    else
      stateD(n.substr(1));
  }   
}
  
// Function for transition
// state C
function stateC(n)
{
  document.write("string accepted");
}
   
// Function for transition
// state D
function stateD(n)
{
  if (n.length == 0)
    Console.Write("string not accepted");
  else
  {
  
    // State transition to D
    // if the character is 1
    if (n[0] == '1')
      stateD(n.substr(1));
  
    // State transition to E
    // if the character is 0
    else
      stateE(n.substr(1));
  }
}
   
// Function for transition
// state E
function stateE(n)
{
  if (n.length == 0)
    document.write("string not accepted");
  else
  {
  
    // State transition to E
    // if the character is 0
    if(n[0] == '0')
      stateE(n.substr(1));
  
    // State transition to F
    // if the character is 1
    else
      stateF(n.substr(1));
  }
}
   
// Function for transition
// state F
function stateF(n)
{
  if(n.length == 0)
    document.write("string accepted");
  else
  {
    // State transition to D
    // if the character is 1
    if(n[0] == '1')
      stateD(n.substr(1));
  
    // State transition to E
    // if the character is 0
    else
      stateE(n.substr(1));
  }
}
  
     
// Driver Code
 
    let n = "0100101";
  checkstateA(n);
           
</script>

String accepted

Complejidad temporal: O(N)
Espacio auxiliar: O(N)