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

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:

1. Construya FA para significa que tiene un número par de a.
2. Construya FA para medios que tienen cualquier número de b mayor que uno.
3. 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:
dado que DFA tiene los siguientes estados. El estado 3 conduce a la aceptación de la string, mientras que los estados 0, 1, 2 y 4 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)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