Construya un DFA que acepte el lenguaje L = {anbm | n > =1, (m) módulo 3 = 1}

Problema: Construya un DFA que acepte el lenguaje L = {a n b m | n > =1, (m) módulo 3 = 1}.

Explicación:
Para construir el DFA, se deben recordar las siguientes cosas:

(element)^* which means any no of elements, and
(element)^+ = (element).(element)^* which means any no of elements greater than 1.

Ejemplos:

Input: a a b b b           
Output: NOT ACCEPTED
// n = 2 (>=1), m=3 ((3) mod3 != 1)

Input: a a a b        
Output: ACCEPTED
 // n = 3 (>=1), m = 1 ((1) mod 3= 1)

Input: b b b b        
Output: NOT ACCEPTED
// n = 0(must be >=1), m = 4 ((4) mod 3 = 1) 

Enfoques:
Su construcción debe contener los siguientes pasos:

  • Paso 1: Construir FA para un^+medios que tienen cualquier número de a mayor que uno.
  • Paso 2: Construir FA para bmedios que tienen exactamente
  • Paso 3: Construir FA para (bbb)^*medios que tienen b igual a múltiplo de 3 .
  • Paso 4: concatene los tres FA y cree un solo DFA. Mantenga siempre el orden de a, b y c.
    • Dado que DFA tiene los siguientes estados. El estado 2 conduce a la aceptación de la string. Mientras que los estados 0, 1, 3, 4 y 5 conducen al rechazo de la string.

      Diagrama de transición de estado de DFA:

      Veamos el código para la demostración:

      C/C++

      // C program to implement DFS that accepts
      // all string which follow the language
      // L = { a^n b^m ; n >=1, (m)mod 3=1}
      #include <stdio.h>
      #include <string.h>
        
      // dfa tells the number associated
      // string end in which state.
      int dfa = 0;
        
      // This function is for
      // the starting state (Q0)of DFA
      void start(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 5;
          }
        
          // -1 is used to check for any invalid symbol
          else {
              dfa = -1;
          }
      }
        
      // This function is for the first state (Q1) of DFA
      void state1(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 2;
          }
          else {
              dfa = -1;
          }
      }
        
      // This function is for the second state (Q2) of DFA
      void state2(char c)
      {
          if (c == 'b') {
              dfa = 3;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
        
      // This function is for the third state (Q3)of DFA
      void state3(char c)
      {
          if (c == 'b') {
              dfa = 4;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
        
      // This function is for the forth state (Q4)of DFA
      void state4(char c)
      {
          if (c == 'b') {
              dfa = 2;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
        
      // This function is for the fifth state (Q5) of DFA
      void state5(char c)
      {
          dfa = -1;
      }
        
      int isAccepted(char str[])
      {
          // store length of string
          int i, len = strlen(str);
        
          for (i = 0; i < len; i++) {
              if (dfa == 0)
                  start(str[i]);
        
              else if (dfa == 1)
                  state1(str[i]);
        
              else if (dfa == 2)
                  state2(str[i]);
        
              else if (dfa == 3)
                  state3(str[i]);
        
              else if (dfa == 4)
                  state4(str[i]);
        
              else if (dfa == 5)
                  state5(str[i]);
        
              else
                  return 0;
          }
          if (dfa == 2)
              return 1;
          else
              return 0;
      }
        
      // driver code
      int main()
      {
          char str[] = "aaabbbb";
          if (isAccepted(str))
              printf("ACCEPTED");
          else
              printf("NOT ACCEPTED");
          return 0;
      }
        
      // This code is contributed by SHUBHAMSINGH10.

      Java

      // Java program to implement DFS that accepts
      // all string which follow the language
      // L = { a^n b^m ; n >=1, (m)mod 3=1}
      import java.util.*;
      class GFG {
         
      // dfa tells the number associated
      // string end in which state.
      static int dfa = 0;
         
      // This function is for
      // the starting state (Q0)of DFA
      static void start(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 5;
          }
         
          // -1 is used to check for any invalid symbol
          else {
              dfa = -1;
          }
      }
         
      // This function is for the first state (Q1) of DFA
      static void state1(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 2;
          }
          else {
              dfa = -1;
          }
      }
         
      // This function is for the second state (Q2) of DFA
      static void state2(char c)
      {
          if (c == 'b') {
              dfa = 3;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
         
      // This function is for the third state (Q3)of DFA
      static void state3(char c)
      {
          if (c == 'b') {
              dfa = 4;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
         
      // This function is for the forth state (Q4)of DFA
      static void state4(char c)
      {
          if (c == 'b') {
              dfa = 2;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
         
      // This function is for the fifth state (Q5) of DFA
      static void state5(char c)
      {
          dfa = -1;
      }
         
      static int isAccepted(char str[])
      {
          // store length of string
          int i, len = str.length;
         
          for (i = 0; i < len; i++) {
              if (dfa == 0)
                  start(str[i]);
         
              else if (dfa == 1)
                  state1(str[i]);
         
              else if (dfa == 2)
                  state2(str[i]);
         
              else if (dfa == 3)
                  state3(str[i]);
         
              else if (dfa == 4)
                  state4(str[i]);
         
              else if (dfa == 5)
                  state5(str[i]);
         
              else
                  return 0;
          }
          if (dfa == 2)
              return 1;
          else
              return 0;
      }
         
      // Driver code
      public static void main(String[] args) {
         char str[] = "aaabbbb".toCharArray();
          if (isAccepted(str)==1)
              System.out.println("ACCEPTED");
          else
              System.out.println("NOT ACCEPTED");
          }
      }
        
      // This code is contributed by Rajput-Ji

      Python 3

      # Python3 program to implement DFS that accepts   
      # all Stringing which follow the language   
      # L = {a ^ n b ^ m | n >= 1, (m)mod 3 = 1 }
            
      # This function is for the dfa = starting  
      # dfa = state (zeroth) of DFA   
      def start(c):  
          if (c == 'a'):  
              dfa = 1
          elif (c == 'b'):  
              dfa = 5
                
          # -1 is used to check for any  
          # invalid symbol   
          else:  
              dfa = -1
          return dfa  
            
      # This function is for the first   
      # dfa = state of DFA   
      def state1(c):   
          if (c == 'a'):  
              dfa = 1
          elif (c == 'b'):  
              dfa = 2
          else:  
              dfa = -1
          return dfa  
            
      # This function is for the second   
      # dfa = state of DFA   
      def state2(c):  
          if (c == 'b'):  
              dfa = 3
          elif (c == 'a'):  
              dfa = 5
          else:  
              dfa = -1
          return dfa  
            
      # This function is for the third   
      # dfa = state of DFA   
      def state3(c):  
          if (c == 'b'):  
              dfa = 4
          elif (c == 'a'):  
              dfa = 5
          else:  
              dfa = -1
          return dfa  
            
      # This function is for the fouth   
      # dfa = state of DFA   
      def state4(c):  
          if (c == 'b'):  
              dfa = 2
          elif (c == 'a'):  
              dfa = 5
          else:  
              dfa = -1
          return dfa 
            
            
      # This function is for the fifth  
      # dfa = state of DFA   
      def state5(c):  
          dfa = -1
          return dfa  
            
      def isAccepted(String):  
                
          # store length of Stringing   
          l = len(String)  
                
          # dfa tells the number associated  
          # with the present dfa = state  
          dfa = 0
          for i in range(l):   
              if (dfa == 0):   
                  dfa = start(String[i])   
            
              elif (dfa == 1):   
                  dfa = state1(String[i])   
            
              elif (dfa == 2) :  
                  dfa = state2(String[i])   
            
              elif (dfa == 3) :  
                  dfa = state3(String[i])   
            
              elif (dfa == 4) :  
                  dfa = state4(String[i]) 
                
              elif (dfa == 5) :  
                  dfa = state5(String[i])
              else:  
                  return 0
          if(dfa == 2) :  
              return 1
          else:  
              return 0
            
      # Driver code   
      if __name__ == "__main__" :  
          String = "aaabbbb"
          if (isAccepted(String)) :  
              print("ACCEPTED")   
          else:  
              print("NOT ACCEPTED")   
        
      # This code is contributed by SHUBHAMSINGH10.

      C#

      // C# program to implement DFS that accepts
      // all string which follow the language
      // L = { a^n b^m ; n >=1, (m)mod 3=1}
      using System;
      public class GFG {
          
      // dfa tells the number associated
      // string end in which state.
      static int dfa = 0;
          
      // This function is for
      // the starting state (Q0)of DFA
      static void start(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 5;
          }
          
          // -1 is used to check for any invalid symbol
          else {
              dfa = -1;
          }
      }
          
      // This function is for the first state (Q1) of DFA
      static void state1(char c)
      {
          if (c == 'a') {
              dfa = 1;
          }
          else if (c == 'b') {
              dfa = 2;
          }
          else {
              dfa = -1;
          }
      }
          
      // This function is for the second state (Q2) of DFA
      static void state2(char c)
      {
          if (c == 'b') {
              dfa = 3;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
          
      // This function is for the third state (Q3)of DFA
      static void state3(char c)
      {
          if (c == 'b') {
              dfa = 4;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
          
      // This function is for the forth state (Q4)of DFA
      static void state4(char c)
      {
          if (c == 'b') {
              dfa = 2;
          }
          else if (c == 'a') {
              dfa = 5;
          }
          else {
              dfa = -1;
          }
      }
          
      // This function is for the fifth state (Q5) of DFA
      static void state5(char c)
      {
          dfa = -1;
      }
          
      static int isAccepted(char []str)
      {
          // store length of string
          int i, len = str.Length;
          
          for (i = 0; i < len; i++) {
              if (dfa == 0)
                  start(str[i]);
          
              else if (dfa == 1)
                  state1(str[i]);
          
              else if (dfa == 2)
                  state2(str[i]);
          
              else if (dfa == 3)
                  state3(str[i]);
          
              else if (dfa == 4)
                  state4(str[i]);
          
              else if (dfa == 5)
                  state5(str[i]);
          
              else
                  return 0;
          }
          if (dfa == 2)
              return 1;
          else
              return 0;
      }
          
      // Driver code
      public static void Main(String[] args) {
         char []str = "aaabbbb".ToCharArray();
          if (isAccepted(str)==1)
              Console.WriteLine("ACCEPTED");
          else
              Console.WriteLine("NOT ACCEPTED");
          }
      }
      // This code has been contributed by 29AjayKumar

      Producción:

ACCEPTED

Publicación traducida automáticamente

Artículo escrito por SHUBHAMSINGH10 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 *