Programa para construir un DFA que acepte el lenguaje L = {anbm | n módulo 2=0, m≥1}

Requisito previo : problema de introducción de autómatas finitos : diseñe un autómata finito determinista (DFA) para aceptar el lenguaje
$L = \{a^nb^m | n\mod 2=0, m\geq 1\}$

La expresión regular para el idioma anterior L es,

L = (aa)*.b⁺

Ejemplos:

Input:  a a b b b           
Output:  ACCEPTED
// n = 2 (even) m=3 (>=1)

Input:  a a a b b b         
Output:  NOT ACCEPTED
 // n = 3 (odd), m = 3

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

Enfoques:
Hay 3 pasos implicados que dan como resultado la aceptación de la string:

Construya FA para $(aaa)^*$ significa que tiene un número par de a.
Construya FA para $b ^ +$ medios que tienen cualquier número de b mayor que uno.
Concatene los dos FA y cree un solo DFA.

Cualquier otro resultado de combinación es el rechazo de la string de entrada.

Descripción:

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)mod 2=0, m>=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 = 3;
    }
  
    // -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 = 2;
    }
    else if (c == 'b') {
        dfa = 4;
    }
    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 = 1;
    }
    else {
        dfa = -1;
    }
}
  
// This function is for the third state (Q3)of DFA
void state3(char c)
{
    if (c == 'b') {
        dfa = 3;
    }
    else if (c == 'a') {
        dfa = 4;
    }
    else {
        dfa = -1;
    }
}
  
// This function is for the fourth state (Q4) of DFA
void state4(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
            return 0;
    }
    if (dfa == 3)
        return 1;
    else
        return 0;
}
  
// driver code
int main()
{
    char str[] = "aaaaaabbbb";
    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)mod 2=0, m>=1 }
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 = 3;
    }
  
    // -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 = 2;
    }
    else if (c == 'b')
    {
        dfa = 4;
    }
    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 = 1;
    }
    else 
    {
        dfa = -1;
    }
}
  
// This function is for the
// third state (Q3)of DFA
static void state3(char c)
{
    if (c == 'b') 
    {
        dfa = 3;
    }
    else if (c == 'a')
    {
        dfa = 4;
    }
    else 
    {
        dfa = -1;
    }
}
  
// This function is for the
// fourth state (Q4) of DFA
static void state4(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
            return 0;
    }
    if (dfa == 3)
        return 1;
    else
        return 0;
}
  
// Driver code
public static void main(String []args) 
{
    char str[] = "aaaaaabbbb".toCharArray();
    if (isAccepted(str) == 1)
        System.out.printf("ACCEPTED");
    else
        System.out.printf("NOT ACCEPTED");
}
}
  
// This code is contributed by 29AjayKumar

Python 3

# Python3 program to implement DFS that accepts   
# all Stringing which follow the language   
# L = {a ^ n b ^ m (n)mod 2 = 0, m>= 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 = 3
          
    # -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 = 2
    elif (c == 'b'):  
        dfa = 4
    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 = 1
    else:  
        dfa = -1
    return dfa  
      
# This function is for the third   
# dfa = state of DFA   
def state3(c):  
    if (c == 'b'):  
        dfa = 3
    elif (c == 'a'):  
        dfa = 4
    else:  
        dfa = -1
    return dfa  
      
# This function is for the fourth  
# dfa = state of DFA   
def state4(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])   
        else:  
            return 0
    if(dfa == 3) :  
        return 1
    else:  
        return 0
      
# Driver code   
if __name__ == "__main__" :  
    String = "aaaaaabbbb"
    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)mod 2=0, m>=1 }
using System;
      
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 = 3;
    }
  
    // -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 = 2;
    }
    else if (c == 'b')
    {
        dfa = 4;
    }
    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 = 1;
    }
    else
    {
        dfa = -1;
    }
}
  
// This function is for the
// third state (Q3)of DFA
static void state3(char c)
{
    if (c == 'b') 
    {
        dfa = 3;
    }
    else if (c == 'a')
    {
        dfa = 4;
    }
    else
    {
        dfa = -1;
    }
}
  
// This function is for the
// fourth state (Q4) of DFA
static void state4(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
            return 0;
    }
    if (dfa == 3)
        return 1;
    else
        return 0;
}
  
// Driver code
public static void Main(String []args) 
{
    char []str = "aaaaaabbbb".ToCharArray();
    if (isAccepted(str) == 1)
        Console.Write("ACCEPTED");
    else
        Console.Write("NOT ACCEPTED");
}
}
  
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP program to implement DFS that accepts 
// all string which follow the language 
// L = { a^n b^m ;(n)mod 2=0, m>=1 } 
  
// This function is for the starting 
// state (zeroth) of DFA 
function start($c, &$dfa)
{
    if($c == 'a') 
        $dfa = 1; 
          
    elseif ($c == 'b') 
        $dfa = 3; 
      
    // -1 is used to check for any 
    // invalid symbol 
    else $dfa = -1; 
}
  
// This function is for the first 
// state of DFA 
function state1($c, &$dfa)
{
    if ($c == 'a')
        $dfa = 2; 
    elseif ($c == 'b') 
        $dfa = 4; 
    else
        $dfa = -1; 
  
}
  
// This function is for the second 
// state of DFA 
function state2($c, &$dfa)
{
    if ($c == 'b') 
        $dfa = 3; 
    elseif ($c == 'a') 
        $dfa = 1; 
    else 
        $dfa = -1; 
}
  
// This function is for the third 
// state of DFA 
function state3($c, &$dfa)
{
    if ($c == 'b') 
        $dfa = 3; 
    elseif ($c == 'a') 
        $dfa = 4; 
    else 
        $dfa = -1; 
}
  
// This function is for the fourth 
// state of DFA 
function state4($c, &$dfa)
{
    $dfa = -1; 
}
  
  
function isAccepted($str,&$dfa)
{
    // store length of string 
    $i = 0; $len = sizeof($str); 
    for ($i = 0; $i < $len; $i++) 
    { 
        if ($dfa == 0) 
            start($str[$i], $dfa); 
  
        elseif ($dfa == 1) 
            state1($str[$i], $dfa); 
  
        elseif ($dfa == 2) 
            state2($str[$i], $dfa); 
  
        elseif ($dfa == 3) 
            state3($str[$i], $dfa); 
  
        elseif ($dfa == 4) 
            state4($str[$i], $dfa); 
        else
            return 0; 
              
    } 
    if($dfa == 3) 
        return 1; 
    else
    return 0; 
}
  
// Driver Code 
  
// dfa tells the number associated 
// with the present state 
$dfa = 0;
$str = array("a", "a", "a", "a", "a", 
             "a", "b", "b", "b", "b");
  
if (isAccepted($str, $dfa) != 0) 
    echo "ACCEPTED"; 
else
    echo "NOT ACCEPTED"; 
  
// This code is contributed 
// by Adesh Singh
?>

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#

PHP

Deja una respuesta Cancelar la respuesta