Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same state given any letter).

How would I translate that in my grammar?

Thanks in advance

share|improve this question
1  
It won’t translate directly: you’re grammar simply won’t generate strings that would put the NFA in the death state. (I’ve always called it the garbage state, myself.) –  Brian M. Scott Dec 13 '12 at 22:09
    
so just ignore this state and the transitions to it when I make the grammar? –  DanielY Dec 13 '12 at 22:14
1  
If you’re using some algorithm to do the translation, it should have a provision for dealing with such a state. If not, you’ll have to take into account the effect of the death state; it just won’t correspond to any actual entity in the grammar. –  Brian M. Scott Dec 13 '12 at 22:17
    
well, ok, thanks! how can I accept your answer if it's in a comment? –  DanielY Dec 13 '12 at 22:23
    
I’ll make a short answer out of it; it’ll take just a minute. (And I’ll get rid of the bloomin’ misspelling!) –  Brian M. Scott Dec 13 '12 at 22:25
add comment

1 Answer 1

up vote 0 down vote accepted

It won’t translate directly: your grammar simply won’t generate strings that would put the NFA into the death state (a much more dramatic term than my garbage state). If you’re using some algorithm to do the translation, it should have a provision for dealing with such a state. If not, you’ll you’ll have to take into account the effect of the death state, but it won’t correspond to any actual entity in the grammar.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.