
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
February 2nd, 2012, 03:22 AM  #1 
Joined: Sep 2009 Posts: 9 Thanks: 0  DFA to Regular Expression
Hey, I'm hoping someone can help me understand this. How did (b) become (c)? I'm familiar with the GNFA algorithm, but when I try to get rid of state1 there are too many links that's throwing me off.. Thanks! 
February 2nd, 2012, 09:25 AM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,860 Thanks: 94  Re: DFA to Regular Expression Quote:
Then you can contract the loop between 1 and 2 by noticing that it just gives you aa, so each time you go to the state you can get either an aa or a b, any number of times each. Do the same with the loop between 1 and 3. But now you've removed the possibility to go from an (aa or a b) at 2 to a bb at 3, so add those arrows in with what it would take to go between them.  

Tags 
dfa, expression, regular 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Regular Expression to NFA  seadoo14  Applied Math  3  October 21st, 2011 04:47 AM 
Proof check: Convert DFA into Regular Expression  extatic  Computer Science  0  April 28th, 2011 08:15 PM 
Rewrite the expression as an algebraic expression in x  kev085  Algebra  1  April 24th, 2009 04:06 AM 
converting quadratic expression to a different expression  woodman5k  Algebra  2  October 10th, 2007 04:53 PM 
Proof check: Convert DFA into Regular Expression  extatic  Applied Math  0  January 1st, 1970 12:00 AM 