2
$\begingroup$

It's clear that we can only have a single start state in G-NFA's but I would like to know why we can't have more than one accepting state in G-NFA's.I think it's better to have more accepting states so that we could avoid epsilon transitions.

Is this only a rule that might make conversion of NFA to Regular expressions simpler or is there any specific reason.If this rule makes the conversion simpler could anyone tell the reason behind it.

$\endgroup$

1 Answer 1

3
$\begingroup$

A GNFA (generalized NFA) can have any number of accepting states, just like an ordinary DFA/NFA.

But, as you suspect, the conversion of NFAs to regular expressions is easier if there's only one accepting state. At each step of the conversion algorithm, you remove one state that isn't the start state and isn't the accepting state, and you modify the regular expressions that label the edges of the remaining transitions. The point is that, eventually, you end up with an automaton that has a start state, an accepting state, a single transition between the two and nothing else. The transition is labelled with a regular expression $R$ and the only possible transition from the start state is to reach the accepting state by reading some input that matches $R$. Therefore, $R$ matches exactly the language of the machine.

If you had multiple accepting states, you'd end up with an automaton that had one start state and multiple accepting states. In particular, there could be transitions between different accepting states. That means there's no unique way of reaching an accepting state so it's not at all obvious how to produce a single regular expression that corresponds to the automaton. You'd probably need to use a modified version of the standard algorithm to "crunch" those accepting states down to a single one. But that seems much more complicated than just having a single accepting state and dealing with a few harmless epsilon-transitions.

$\endgroup$
8
  • 1
    $\begingroup$ :Do you have time to explain a bit more about G-NFA's? $\endgroup$
    – justin
    Commented Feb 12, 2016 at 8:56
  • 1
    $\begingroup$ @justin, presumably you have a textbook, class notes, a TA or lecturer to ask for this... if you still don't undestand some particular point, then ask here. This is a question and answer site, not a question and you shall get private lessons site. $\endgroup$
    – vonbrand
    Commented Feb 12, 2016 at 16:15
  • $\begingroup$ @justin No, sorry, I don't have time for such an open-ended question. If you just want to learn more about a subject look in a textbook (Sipser's Introduction to the Theory of Computation contains a fairly detailed section on GNFAs) or ask your teachers. There's not a lot of point in me essentially writing a section of a textbook chapter in the hope that it'll be useful to you. $\endgroup$ Commented Feb 12, 2016 at 16:17
  • $\begingroup$ @DavidRicherby:Sorry to bother you too much but the last question that stops me down.The question is to check whether a finite automata accepts regular expression.So can I write 'other than R' for one transition and R for other transition using epsilon transitions so we are just guessing each transition but haven't read any symbol as you said in the previous chat. $\endgroup$
    – justin
    Commented Feb 15, 2016 at 6:37
  • 1
    $\begingroup$ Justin, I'm sorry but it's not my responsibility to answer every single question that you have. I don't have time to be your personal tutor. $\endgroup$ Commented Feb 15, 2016 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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