d2jsp
Log InRegister
d2jsp Forums > Off-Topic > General Chat > Homework Help > Programming Help > Nfa To Dfa
Add Reply New Topic New Poll
Member
Posts: 7,566
Joined: Mar 12 2013
Gold: Locked
Apr 7 2016 06:44am
Http://i68.tinypic.com/308w37n.jpg

How do you convert this from NFA to DFA using subset construction algorithm? Thanks
Member
Posts: 7,566
Joined: Mar 12 2013
Gold: Locked
Apr 7 2016 07:32am
And theres another thing im struggling with

How do you write a regular expression for the the letters {o,g} which produces arbitrary sequences of length n where n is divisible by 2 or 3
Member
Posts: 17,592
Joined: Mar 13 2009
Gold: 0.00
Apr 7 2016 07:43am
You might want to post here http://forums.d2jsp.org/forum.php?f=120
Member
Posts: 12,786
Joined: May 17 2013
Gold: 4,010.00
Apr 7 2016 09:15am
NFA -> DFA is done by mapping all subsets you can reach from any other subset, and keeping the map in order with the transitions (so if you can reach state 3 with an A followed by an epsilon transition from state 1, the transition from any set containing 1 to a set containing 3 HAS to have the transition A.

What you end up with is a DFA with the minimum amount of states needed to map the functionality of the NFA in question.

In your example it would be (assuming eps is an epsilon transition!) these groups you would have to map:

{1,2,4}, {2}, {4}, {3,6}, {5,6} and {6}.

Regular expressions are not suited for doing what you want, as you don't evaluate values with a regular expression.
You probably could do it, but it's certainly not a good idea.

If you just need a regex that only accepts {o,g} divisible by 2 or 3 you could construct a NFA and convert it to a GNFA.
You shouldn't do it based on the word length, but rather the number of o's or g's (and both) that can come before/after one another.

This post was edited by Klexmoo on Apr 7 2016 09:34am
Member
Posts: 7,566
Joined: Mar 12 2013
Gold: Locked
Apr 10 2016 09:20am
thank you very much, that was a great help!
Member
Posts: 12,786
Joined: May 17 2013
Gold: 4,010.00
Apr 11 2016 02:01pm
Quote (gladiola @ 10 Apr 2016 17:20)
thank you very much, that was a great help!


You are welcome.
Go Back To Homework Help Topic List
Add Reply New Topic New Poll