What's the regex corresponding to this DFA?
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.
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:
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 .
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
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
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
Jack, basically there can be two regex for this DFA. first can be AB*CD*A, second can be AE*F*
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*
上一篇: NFA DFA和正则表达式到转换表
下一篇: 与此DFA对应的正则表达式是什么？