My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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!
Attached Images
File Type: jpg math.jpg (77.8 KB, 591 views)
l flipboi l is offline  
 
February 2nd, 2012, 09:25 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 13,740
Thanks: 328

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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.
CRGreathouse is online now  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2014 My Math Forum. All rights reserved.