Wednesday, November 28, 2012

From FSA to regular expression

with given a FSA model, M, we can construct a regular expression that denotes precisely the language accepted by M.

Question.2 from tutorial exercise #8  

From the DFSA, shown in the previous post of "DFSA example";
devise the regular expression that denotes the same language.

the DFSA to start with:












- Remove every state except the accepting state and the initial state.
first, try to remove q3 state; x has an odd number of 0s and an odd number of 1s
then we get a DFSA
















then, we remove q2 state; x has an even number of 0s and an odd number of 1s
then we get a DFSA












Devised the regular expression:  
                                          


This particular tutorial exercise question really got me to understand, how devising a regular expression from FSA, works! thanksful ^^; 



No comments:

Post a Comment