World's most popular travel blog for travel bloggers.

[Answers] Why there's a single accepting state in G-NFA's?

, , No Comments
Problem Detail: 

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.

Asked By : justin

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52997

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback