Welcome! Log In Create A New Profile


Cohen ch8 problem14(ix)

Posted by kiolb 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
avatar Cohen ch8 problem14(ix)
June 02, 2008 01:40AM

Not sure how to determine when no "dead-end" state is needed!

I do not see where in the algorithm for NFA to FA that this is determined.

Re: Cohen ch8 problem14(ix)
June 02, 2008 02:35PM
I assume your question is from Chapter 7 Problem 14(iv). Constructing an NFA does not have as many restriction as constructing an FA, i.e. there is no need to have an outgoing edge for each letter of the alphabet from each state when constructing an NFA. Thus, an dead-end state can be eliminated when converting an FA into an NFA.
Re: Cohen ch8 problem14(ix)
June 02, 2008 05:28PM
kiolb if you look at the NFA only the final state lacks outgoing edges ( a or b ). In the transition table you'll see there is no situation where there is a z state that is only equal to this final x state, so theres always somewhere to go! (cause the other two states both have a and b edges)

Hope that makes sense =o
avatar Re: Cohen ch8 problem14(ix)
June 02, 2008 07:15PM
Oops. Meant ch7 prob14(ix). Did not have to do 14(iv).

Thanks for the replies.
The question asks to change NFA to FA.
In the example on pg138. The final state on the NFA has no outgoing edges, but the equivalent FA has a dead-end state.
The answer to 14(v) has a dead-end state.

Back to 14(ix). State z2, a or b could be in x2, which should then go to a dead-end state, according to the algorithm and the example on pg138.

The answer in the study guide, without using a dead-end, or null state, looks reasonable. But if the algorithm is followed, where is a or b in x2 going to go?
Is it because a or b in z2 has other choices that the dead-end state can be ignored? If so, which rule determines this? This was my original question.

Hope this has clarified my question.
avatar Re: Cohen ch8 problem14(ix)
June 02, 2008 08:15PM
Hi, may have answered my own question.smile

[x1 or x2 or x3 or "null"] is equal to [x1 or x2 or x3]

I was looking at the dead-end state as an actual state, which it is not.

Is this correct?


edited 20080603 15:53
Explained in Cohen pg131 thumbs up
Re: Cohen ch8 problem14(ix)
June 02, 2008 10:01PM
Ah what I meant is, the only way to the dead-end state in that FA is through the final state (X2), because the other states have adequate edges.

So if there was a new state z4 = x2 then you'd have to have a dead-end state where the a and b of z4 go to.

Glad you got it right =D
Sorry, only registered users may post in this forum.

Click here to login