Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

drawing minmal DFA for the given regular expression

What is the direct and easy approach to draw minimal DFA, that accepts the same language as of given Regular Expression(RE).
I know it can be done by:

Regex ---to----► NFA ---to-----► DFA ---to-----► minimized DFA

But is there any shortcut way? like for (a+b)*ab

like image 539
Niraj Rana Avatar asked Dec 07 '12 20:12

Niraj Rana


People also ask

How do I create a regular expression in DFA?

Utility – To construct DFA from a given regular expression, we can first construct an NFA for the given expression and then convert this NFA to DFA by a subset construction method. But to avoid this two-step procedure, the other way round is to directly construct a DFA for the given expression.

How many minimum states are there in DFA for regular expression a * b *?

Somewhere it was explained that we need "trap" state, so the answer would be 4.

How do we convert regular expression to NFA or DFA?

This method is given below: Step 1: Design a transition diagram for given regular expression, using NFA with ε moves. Step 2: Convert this NFA with ε to NFA without ε. Step 3: Convert the obtained NFA to equivalent DFA.


1 Answers

Regular Expression to DFA

Although there is NO algorithmic shortcut to draw DFA from a Regular Expression(RE) but a shortcut technique is possible by analysis not by derivation, it can save your time to draw a minimized dfa. But off-course the technique you can learn only by practice. I take your example to show my approach:

(a + b)*ab   

First, think about the language of the regular expression. If its difficult to sate what is the language description at first attempt, then find what is the smallest possible strings can be generate in language then find second smallest.....

Keep memorized solution of some basic regular expressions. For example, I have written here some basic idea to writing left-linear and right-linear grammars directly from regular expression. Similarly you can write for construing minimized dfa.

In RE (a + b)*ab, the smallest possible string is ab because using (a + b)* one can generate NULL(^) string. Second smallest string can be either aab or bab. Now one thing we can easily notice about language is that any string in language of this RE always ends with ab (suffix), Whereas prefix can be any possible string consist of a and b including ^.

Also, if current symbol is a; then one possible chance is that next symbol would be a b and string end. Thus in dfa we required, a transition such that when ever a b symbol comes after symbol a, then it should be move to some of the final state in dfa.

Next, if a new symbol comes on final state then we should move to some non-final state because any symbol after b is possible only in middle of some string in language as all language string terminates with suffix 'ab'.

So with this knowledge at this stage we can draw an incomplete transition diagram like below:

--►(Q0)---a---►(Q1)---b----►((Qf))

Now at this point you need to understand: every state has some meaning for example

(Q0) means = Start state
(Q1) means = Last symbol was 'a', and with one more 'b' we can shift to a final state
(Qf) means = Last two symbols was 'ab'

Now think what happens if a symbol a comes on final state. Just more to state Q1 because this state means last symbol was a. (updated transition diagram)

--►(Q0)---a---►(Q1)---b----►((Qf))  
                ▲-----a--------|  

But suppose instead of symbol a a symbol b comes at final state. Then we should move from final state to some non-final state. In present transition graph in this situation we should make a move to initial state from final state Qf.(as again we need ab in string for acceptation)

--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|  

This graph is still incomplete! because there is no outgoing edge for symbol a from Q1. And for symbol a on state Q1 a self loop is required because Q1 means last symbol was an a.

                a-  
                ||
                ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|     

Now I believe all possible out-going edges are present from Q1 & Qf in above graph. One missing edge is an out-going edge from Q0 for symbol b. And there must be a self loop at state Q0 because again we need a sequence of ab so that string can be accept. (from Q0 to Qf shift is possible with ab)

    b-          a-  
    ||          ||
    ▼|          ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|      

Now DFA is complete!

Off-course the method might look difficult at first few tries. But if you learn to draw this way you will observe improvement in your analytically skills. And you will find this method is quick and objective way to draw DFA.

* In the link I given, I described some more regular expressions, I would highly encourage you to learn them and try to make DFA for those regular expressions too.

like image 168
Grijesh Chauhan Avatar answered Oct 12 '22 20:10

Grijesh Chauhan