DFA que comienza con ‘a’ pero no contiene la substring ‘aab’

Posted on by Rudeus Greyrat

Requisito previo: Introducción a los autómatas finitos deterministas 
Construya un DFA que acepte strings str que comiencen con el alfabeto de entrada ‘a’ pero que no contengan ‘aab’ como una substring sobre la entrada {a, b} .

Ejemplos: 

Entrada: str = “babba” 
Salida: No aceptado 
Explicación: 
La string dada no comienza con ‘a’.

Entrada: str = “abbaaaaa” 
Salida: Aceptada 
Explicación: 
La string dada comienza con ‘a’ y no contiene “aab” como substring. 
 

Enfoque: 
la tabla de transición ayuda a comprender cómo se produce la transición de cada estado en los alfabetos de entrada. En la tabla de transición, el estado inicial está representado por —> y el estado final está representado por * . Hay 3 estados finales, uno inicial y otro muerto. 

Tabla de transición de estado del DFA dado: 
 

ESTADO ENTRADA (a) ENTRADA (b)
—> Un B* Q (estado muerto)
B* C* D*
C* C* Q (estado muerto)
D* B* D*
Q (estado muerto) Q (estado muerto) Q (estado muerto)

A continuación se muestra el diagrama DFA: 

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

C++

// C++ code for the above DFA
#include <bits/stdc++.h>
using namespace std;
void stateQ(string);
void stateA(string);
void stateB(string);
void stateC(string);
void stateD(string);
 
// Function for state Q
// transition
void stateQ(string n)
{
  // In dead state
  // it shows string
  // not accepted
  cout << ("Not Accepted");
}
 
// Function for state A
// transition
void stateA(string n)
{
  // If at index 0
  // 'a' if found then
  // call stateB function
  // with passing n[1:] to it
  if (n[0] == 'a')
    stateB(n.substr(
           1, n.length() + 1));
 
  // If at index 0
  // 'b' if found then
  // call stateQ function
  // with passing n to it
  else
    stateQ(n);
}
 
// Function for state B transition
void stateB(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    cout << ("Accepted");
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateC(n.substr(
             1, n.length() - 1));
 
    // If at index 0
    // 'b' if found then
    // call stateD function
    // with passing n[1:] to it
    else
      stateD(n.substr(
             1, n.length() - 1));
  }
}
 
// Function for state C
// transition
void stateC(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    cout << ("Accepted");
 
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateC(n.substr(
             1, n.length() + 1));
 
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
      stateQ(n);
  }
}
 
// Function for state D
// transition
void stateD(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    cout << ("Accepted");
 
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateB function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateB(n.substr(
             1, n.length() + 1));
 
    // If at index 0
    // 'b' if found then
    // call stateD function
    // with passing n[1:] to it
    else
      stateD(n.substr(
             1, n.length() + 1));
  }
}
 
// Driver code
int main()
{
  // Take string input
  string n = "aaaba";
 
  // Call stateA to check
  // the input
  stateA(n);
}
 
// This code is contributed by Chitranayal

Java

// Java code for the
// above DFA
import java.util.*;
 
class GFG{
      
// Function for state
// A transition   
static void stateA(String n)
{
   
  // If at index 0
  // 'a' if found then
  // call stateB function
  // with passing n[1:] to it
  if (n.charAt(0) == 'a')
  {
    stateB(n.substring(1));
  }
   
  // If at index 0
  // 'b' if found then
  // call stateQ function
  // with passing n to it   
  else
  {
    stateQ(n);  
  }
}
   
// Function for transition
// state B        
static void stateB(String n)
{
   
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length() == 0)
  {
    System.out.print("Accepted");
  }
  else
  {
     
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n.charAt(0) == 'a')
      stateC(n.substring(1));
  
    // If at index 0
    // 'b' if found then
    // call stateD function
    // with passing n[1:] to it
    else
      stateD(n.substring(1));
  }    
}
  
// Function for transition
// state C
static void stateC(String n)
{
   
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    System.out.print("Accepted");
  else
  {
     
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n.charAt(0) == 'a')
      stateC(n.substring(1));
  
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
      stateQ(n);
  }
}
  
// Function for transition
// state D
static void stateD(String n)
{
   
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    System.out.print("Accepted");
  else
  {
     
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n.charAt(0) == 'a')
    {
      stateB(n.substring(1));
    }
  
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
    {
      stateD(n.substring(1));
    }
  }
}
  
// Function for state Q
// transition
static void stateQ(String n)
{
   
  // In dead state
  // it shows String
  // not accepted
  System.out.print("Not Accepted");
}
      
// Driver code
public static void main(String []args)
{
   
  // Take String input
  String n ="aaaba";
   
  // Call stateA to check the input
  stateA(n);
}
}
 
// This code is contributed by pratham76

Python3

# Python3 code for the above DFA
 
# Function for state A transition
def stateA(n):
     
    # If at index 0
    # 'a' if found then
    # call stateB function
    # with passing n[1:] to it
    if (n[0]=='a'):
        stateB(n[1:])
         
    # If at index 0
    # 'b' if found then
    # call stateQ function
    # with passing n to it   
    else:
        stateQ(n)
 
# Function for state B transition
def stateB(n):
     
    # Length of string
    # become 0 then
    # print Accepted
    if(len(n)== 0):
        print("Accepted")
    else:   
        # If at index 0
        # 'a' if found then
        # call stateC function
        # with passing n[1:] to it
        if (n[0]=='a'):
            stateC(n[1:])
             
        # If at index 0
        # 'b' if found then
        # call stateD function
        # with passing n[1:] to it   
        else:
            stateD(n[1:])
 
# Function for state C transition
def stateC(n):  
     
    # Length of string
    # become 0 then
    # print Accepted
    if(len(n)== 0):
        print("Accepted")
         
    else:
        # If at index 0
        # 'a' if found then
        # call stateC function
        # with passing n[1:] to it
        if (n[0]=='a'):
            stateC(n[1:])
             
        # If at index 0
        # 'b' if found then
        # call stateQ function
        # with passing n to it   
        else:
            stateQ(n)
 
# Function for state D transition
def stateD(n):
     
    # Length of string
    # become 0 then
    # print Accepted
    if(len(n)== 0):
        print("Accepted")
         
    else:   
        # If at index 0
        # 'a' if found then
        # call stateB function
        # with passing n[1:] to it
        if (n[0]=='a'):
            stateB(n[1:])
             
        # If at index 0
        # 'b' if found then
        # call stateD function
        # with passing n[1:] to it   
        else:
            stateD(n[1:])
            
# Function for state Q transition
def stateQ(n):
    # In dead state
    # it shows string
    # not accepted
    print("Not Accepted")
     
# Take string input
n ="aaaba"
 
# Call stateA to check the input
stateA(n)

C#

// C# code for the
// above DFA
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
     
// Function for state
// A transition   
static void stateA(string n)
{
  // If at index 0
  // 'a' if found then
  // call stateB function
  // with passing n[1:] to it
  if (n[0] == 'a')
  {
    stateB(n.Substring(1));
  }
 
 
  // If at index 0
  // 'b' if found then
  // call stateQ function
  // with passing n to it   
  else
  {
    stateQ(n);  
  }
}
  
// Function for transition
// state B        
static void stateB(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.Length == 0)
  {
    Console.Write("Accepted");
  }
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if(n[0] == 'a')
      stateC(n.Substring(1));
 
    // If at index 0
    // 'b' if found then
    // call stateD function
    // with passing n[1:] to it
    else
      stateD(n.Substring(1));
  }    
}
 
// Function for transition
// state C
static void stateC(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.Length == 0)
    Console.Write("Accepted");
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateC(n.Substring(1));
 
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
      stateQ(n);
  }
}
 
// Function for transition
// state D
static void stateD(string n)
{
  // Length of string
  // become 0 then
  // print Accepted
  if (n.Length == 0)
    Console.Write("Accepted");
  else
  {
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
    {
      stateB(n.Substring(1));
    }
 
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
    {
      stateD(n.Substring(1));
    }
 
  }
}
 
// Function for state Q
// transition
static void stateQ(string n)
{
  // In dead state
  // it shows string
  // not accepted
  Console.Write("Not Accepted");
}
     
// Driver code
public static void Main(string []args)
{
  // Take string input
  string n ="aaaba";
 
  // Call stateA to check the input
  stateA(n);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// JavaScript program to implement
// the above approach
  
// Function for state
// A transition  
function stateA(n)
{
    
  // If at index 0
  // 'a' if found then
  // call stateB function
  // with passing n[1:] to it
  if (n[0] == 'a')
  {
    stateB(n.substr(1));
  }
    
  // If at index 0
  // 'b' if found then
  // call stateQ function
  // with passing n to it  
  else
  {
    stateQ(n); 
  }
}
    
// Function for transition
// state B       
function stateB(n)
{
    
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length == 0)
  {
    document.write("Accepted");
  }
  else
  {
      
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateC(n.substr(1));
   
    // If at index 0
    // 'b' if found then
    // call stateD function
    // with passing n[1:] to it
    else
      stateD(n.substr(1));
  }   
}
   
// Function for transition
// state C
function stateC(n)
{
    
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length == 0)
    document.write("Accepted");
  else
  {
      
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
      stateC(n.substr(1));
   
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
      stateQ(n);
  }
}
   
// Function for transition
// state D
function stateD(n)
{
    
  // length() of String
  // become 0 then
  // print Accepted
  if (n.length() == 0)
    document.write("Accepted");
  else
  {
      
    // If at index 0
    // 'a' if found then
    // call stateC function
    // with passing n[1:] to it
    if (n[0] == 'a')
    {
      stateB(n.substr(1));
    }
   
    // If at index 0
    // 'b' if found then
    // call stateQ function
    // with passing n to it
    else
    {
      stateD(n.substr(1));
    }
  }
}
   
// Function for state Q
// transition
function stateQ(n)
{
    
  // In dead state
  // it shows String
  // not accepted
  document.write("Not Accepted");
}
 
// Driver code
 
    // Take String input
  let n ="aaaba";
    
  // Call stateA to check the input
  stateA(n);
   
  // This code is contributed by sanjoy_62.
</script>
Producción: 

Not Accepted

 

Tiempo Complejidad : O(N)  
Espacio Auxiliar : O(N)

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 *