
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
February 2nd, 2012, 03:22 AM  #1 
Newbie 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: 16,046 Thanks: 928 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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 
Search tags for this page 
Click on a term to search for related topics.

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 