# Cohen ch8 problem14(ix)

Posted by kiolb
Announcements Last Post
myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Cohen ch8 problem14(ix) June 02, 2008 01:40AM Registered: 11 years ago Posts: 423 Rating: 0
Hello.

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.

Thanks
B
 Re: Cohen ch8 problem14(ix) June 02, 2008 02:35PM Registered: 13 years ago Posts: 119 Rating: 0
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 Registered: 12 years ago Posts: 73 Rating: 0
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
 Re: Cohen ch8 problem14(ix) June 02, 2008 07:15PM Registered: 11 years ago Posts: 423 Rating: 0
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.

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.
Regards
B
 Re: Cohen ch8 problem14(ix) June 02, 2008 08:15PM Registered: 11 years ago Posts: 423 Rating: 0
Hi, may have answered my own question.

ie:
[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?

Thanks
B

edited 20080603 15:53
Explained in Cohen pg131
 Re: Cohen ch8 problem14(ix) June 02, 2008 10:01PM Registered: 12 years ago Posts: 73 Rating: 0
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.