0
$\begingroup$

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

  • 0
    I’ll make a short answer out of it; it’ll take just a minute. (And I’ll get rid of the bloomin’ misspelling!)2012-12-13

1 Answers 1

0

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.