Concevoir des automates finis déterministes (Ensemble 10)

Prérequis: Concevoir des automates finis
Dans cet article, nous verrons la conception d’automates finis déterministes (DFA).
Problème-1 : Construction d’un DFA minimal acceptant un ensemble de chaînes sur {a} dans lequel {an | n≥0, n≠2 c’est-à-dire que ‘n’ doit être supérieur à 0 et non égal à 2}.
Explication: La langue souhaitée sera comme:

L1 = {ε, a, aaa, aaaa, aaaaa, ..................}

Ici, ε est pris comme chaîne car la valeur de ‘n’ est supérieure ou égale à zéro et le reste des chaînes a ‘a’ à la puissance de tout nombre naturel positif mais pas 2.
Le langage ci-dessous n’est pas accepté par ce DFA car une partie de la chaîne contient ‘a’ à la puissance 2.

L2 = {aa, aaaaa, ..........}

Ce langage L2 n’est pas accepté par ce DFA requis en raison de sa chaîne contenant ‘a’ à la puissance 2.
Le diagramme de transition d’état de la langue souhaitée sera comme ci-dessous :

Y2

Dans le DFA ci-dessus, l’état initial et final ‘W’ lors de l’obtention de ‘a’ en tant qu’entrée, il transite vers un état final ‘X’. L’état final ‘X’ lors de l’obtention de ‘a’ comme entrée, il transite vers un état ‘Y’. L’état ‘Y’ en obtenant ‘a’ comme entrée, il transite vers un état final ‘Z’ qui, en obtenant n’importe quel nombre de ‘a’, reste dans l’état de lui-même.

Implémentation Python :

Python3

            

def stateW(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatX(n[1:])

       

            

        

def stateX(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else

        

        

        

        if (n[0]=='a'):

            étatY(n[1:])

        

def stateY(n):

    

    

    if(len(n)==0):

        print("string not accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatZ(n[1:])

        

def stateZ(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatZ(n[1:])

            

n=input()

stateW(n)

Problème-2 : Construction d’un DFA minimal acceptant un ensemble de chaînes sur {a} dans lequel {an | n≥0, n≠2, n≠4 c’est-à-dire que ‘n’ doit être supérieur à 0 et non égal à 2 et 4}.
Explication: La langue souhaitée sera comme:

L1 = {ε, a, aa, aaaaa, aaaaaa, .................. }

Ici, ε est pris comme chaîne car la valeur de ‘n’ est supérieure ou égale à zéro et le reste des chaînes a ‘a’ à la puissance de tout nombre naturel positif mais pas 2 et 4.
Le langage ci-dessous n’est pas accepté par ce DFA, car une partie de la chaîne contient ‘a’ à la puissance 2 et 4.

L2 = {aa, aaaaa, aaaaaaaaaa, ............. }

Le diagramme de transition d’état de la langue souhaitée sera comme ci-dessous :

C15

Dans le DFA ci-dessus, l’état initial et final ‘A’ lors de l’obtention de ‘a’ en tant qu’entrée, il transite vers un état final ‘B’. L’état final ‘B’ lors de l’obtention de ‘a’ comme entrée, il transite vers un état ‘C’. L’état ‘C’ lors de l’obtention de ‘a’ comme entrée, il transite vers un état final ‘D’. L’état final ‘D’ lors de l’obtention de ‘a’ comme entrée, il transite vers un état ‘E’. L’état ‘E’ lors de l’obtention de ‘a’ comme entrée, il transite vers un état final ‘F’. L’état final ‘F’ lors de l’obtention de ‘a’ comme entrée, il reste dans l’état de lui-même.

Implémentation Python :

Python3

            

def stateA(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatB(n[1:])

       

            

        

def stateB(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else

        

        

        

        if (n[0]=='a'):

            étatC(n[1:])

        

def stateC(n):

    

    

    if(len(n)==0):

        print("string not accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatD(n[1:])

        

def stateD(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatE(n[1:])

def stateE(n):

    

    

    if(len(n)==0):

        print("string not accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatF(n[1:])

            

def stateF(n):

    

    

    if(len(n)==0):

        print("string accepted")

        

    else:

        

        

        

        if (n[0]=='a'):

            étatF(n[1:])

            

n=input()

stateA(n)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut