My Math Forum DFA to Regular Expression

 Computer Science Computer Science Forum

February 2nd, 2012, 02: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!
Attached Images
 math.jpg (77.8 KB, 591 views)

February 2nd, 2012, 08:25 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: DFA to Regular Expression

Quote:
 Originally Posted by l flipboi l How did (b) become (c)?
Well, first you squish the s and 1 states together -- that's straightforward, right? It's not like the s state was doing anything before...

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

### convert re to dfa code

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post seadoo14 Applied Math 3 October 21st, 2011 04:47 AM extatic Computer Science 0 April 28th, 2011 08:15 PM kev085 Algebra 1 April 24th, 2009 04:06 AM woodman5k Algebra 2 October 10th, 2007 04:53 PM extatic Applied Math 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top