What's the regex corresponding to this DFA?

Question

Here is a DFA from a research project. We created the DFA manually. We are interested in What is Regular Expression that is corresponding to DFA . Certainly, there could be multiple Regular Expressions corresponding to it; we prefer a simpler one.

Answer 1

You have missed the labels in you DFA on self loop at B and E. But because you say for given DFA then only choice for labels is 0 on both loop.

The correct Regular Expression for your DFA is:

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

A brief explanation:

1. You have only one final state that is D. So string can be acceptable if it ends on D. do you notice incoming edge on D is labeled 1 and D has a self loop labeled 0.

2. Start state is A so string can be start with 0 or with 1. Actually there is two loops on A. One starts with 0 and travels through upper graph.
   RE for upper loop is: 00* 10*1

   To understand this:

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

3. To go from A to D in lower graph. RE is 1 (0 + 10)* 1 1
   To understand this:

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

4. The complete RE for DFA is: (answer)

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

   To understand this:

   (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                                
   

Edit as @RedBaron commented does this Regular expression generate string 01110100110 :

well fist check is it accepted by DFA or not:

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

Yes string is accepted by DFA.

How to generate from RE I given in answer, below I have aligned the RE and string.

(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

Only the difficulty you may have to understand: how (0 + 10)* generates 0100? for this check below:

(0 + 10)* be repeat for three times:

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

Answer 2

Jack, basically there can be two regex for this DFA. first can be AB*CD*A, second can be AE*F*

Answer 3

10*110* is for transition from A-B-C-D without the loop in c-B

1(0*(10)*)*110* I think also covers the loop between C and B

0+10*1 is the loop from A-E-F. So you can prefix it to both the expressions

You get (0+10*1)*10*110* without the loop and (0+10*1)*1(0*(10)*)*110* with it

The final expression is thus

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

for transitioning from A to D

Finally on reaching the state D you could get a 1, reach A and repeat the whole thing over again

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

See it in action for some valid and invalid strings for this DFA

Clarification - This regexp is based on regular expressions as accepted by PCRE. So + means 1 or more occurences of a string and * means 0 or more occurences, while | means OR

EDIT The (0*(10)*)* can be written better as (0|(10))* (Thanks to @grijesh-chauhan for pointing me in that direction). So the RE (PCRE based) would be

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

Answer 4

The algorithm you need to use is described here. I strongly recommend reading Michael Sipser's Introduction to the Theory of Computation if you're more interested in the topic.

For your particular DFA, following the algorithm you get this regex:

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