My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
February 2nd, 2012, 02:22 AM   #1
Joined: Sep 2009

Posts: 9
Thanks: 0

DFA to Regular Expression


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..

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

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 offline  

  My Math Forum > Science Forums > Computer Science

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 December 31st, 1969 04:00 PM

Copyright © 2017 My Math Forum. All rights reserved.