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 ⁿ b ^m | n > =1, (m) módulo 3 = 1}.

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

 which means any no of elements, and
 =  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 $b$ medios 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

C/C++

Java

Python 3

C#

Deja una respuesta Cancelar la respuesta