Quelle est la regex correspondant à ce DFA?

Question

Voici un DFA provenant d'un projet de recherche. Nous avons créé le DFA manuellement. Nous nous intéressons à Qu'est-ce que l'expression régulière qui correspond à DFA? Certainement, il pourrait y avoir plusieurs expressions régulières correspondant à lui; nous préférons un plus simple.

Answer 1

Jack, il peut y avoir essentiellement deux regex pour cette DFA. première peut être AB * CD * A, seconde peut être AE * F *

Answer 2

10*110* est de transition entre ABCD sans la boucle dans cB

1(0*(10)*)*110* Je pense couvre également la boucle entre C et B

0+10*1 est la boucle de AEF. Vous pouvez donc le préfixe à la fois les expressions

Vous obtenez (0+10*1)*10*110* sans la boucle et (0+10*1)*1(0*(10)*)*110* avec elle

L'expression finale est donc

(0+10*1)*1(0*(10)*)*110* 

pour la transition de A à D

Enfin en atteignant l'état D, vous pouvez obtenir un 1, atteindre A et répéter le tout à nouveau

((0+10*1)*1(0*(10)*)*110*)(1((0+10*1)*1(0*(10)*)*110*))* 

See it in action pour certaines chaînes valides et non valides pour ce DFA

Précision - Cette expression rationnelle est basée sur les expressions régulières acceptées par PCRE. Donc + signifie 1 ou plusieurs occurences d'une chaîne et * signifie 0 ou plus occurences, tandis que | signifie OR

EDIT Le (0*(10)*)* peut écrire mieux que (0|(10))* (Merci à @ grijesh-Chauhan pour moi pointant dans cette direction). Ainsi, le RE (à base PCRE) serait

((0+10*1)*1(0|(10))*110*)(1((0+10*1)*1(0|(10))*110*))* 

Answer 3

L'algorithme, vous devez utiliser est décrit here. Je vous recommande fortement de lire le Introduction to the Theory of Computation de Michael Sipser si vous êtes plus intéressé par le sujet.

Pour votre DFA particulier, après l'algorithme vous obtenez ce regex:

[(010*1)*1(10*)110*1]*(010*1)*1(10)*110* 

Answer 4

Vous avez manqué les étiquettes en vous DFA sur boucle d'auto à B et E. Mais parce que vous dites pour DFA donné alors Le seul choix pour les étiquettes est 0 sur les deux boucles.

La bonne expression régulière pour votre DFA est:

(00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 

Une brève explication:

1. Vous avez un seul état final qui est D. Donc, la chaîne peut être acceptable si elle se termine par D. remarquez-vous bord entrant sur D est marqué 1 et D a une boucle d'auto marqué 0.

2. L'état de départ est A, donc la chaîne peut commencer par 0 ou avec 1. En fait, il y a deux boucles sur A. On commence par 0 et voyage à travers le graphique supérieur.
   RE boucle supérieure est: 00* 10*1

   Pour comprendre ceci:

   0  0*   1  0*   1 
   
   A-E loop on E  E-F loop on F  F-A 
   

3. Pour aller A-D dans le graphique inférieur. RE est 1 (0 + 10)* 1 1
   Pour comprendre ceci:

   1  (0 + 10)* 1  1 
   A - B loop on B B-C C-D  
   

4. Le RE complet pour DFA est: (réponse)

   (00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 
   

   Pour comprendre ceci:

   (00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 
   
   ^   ^            ^ 
   upper loop A to D   loop on D    * for loop on D  
   
   
            (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1 )* 
            ^ D-A A-A  A-B loop on B, B-c c-D  
           self loop on D         
   

Modifier comme @RedBaron a commenté cette expression régulière ne fait générer chaîne 01110100110:

bien vérifier le poing est-il accepté par DFA ou non:

A - 0 -> E - 1 --- > F - 1 ---> A --- 1 ---> B - 0 ---> B --- 1 ---> C --- 0 --- -> B --- 0 ---> B - 1 -> C --- 1 ---> D --- 0 ---> D

La chaîne de caractères Oui est acceptée par DFA.

Comment générer de RE I donné en réponse ci-dessous j'ai aligné le RE et la chaîne.

(00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 

0^ 1^ 1  1 0100  1 1 0 

Seule la difficulté que vous pourriez avoir à comprendre: comment (0 + 10)* génère 0100? pour cette vérification ci-dessous:

(0 + 10)* être répéter trois fois:

(0 + 10)(0 + 10)(0 + 10) 
0   10 0