2
$\begingroup$

I would like to know whether we could replace the second image with first image since the second image contains less transitions and states than first image even though everyone uses second image to show construction of (a*). NFA 1NFA 2

$\endgroup$
7
  • 1
    $\begingroup$ You can construct the NFA for regular expression $a^*$ using only 2 states. $\endgroup$ Commented Oct 29, 2015 at 7:22
  • 1
    $\begingroup$ What do you mean by "$R^*(a^*)$"? $\endgroup$ Commented Oct 29, 2015 at 9:14
  • $\begingroup$ @DavidRicherby:Oh that was to show that I used a* instead of the common notation R* to show NFA of Kleene Star. $\endgroup$
    – justin
    Commented Oct 29, 2015 at 10:16
  • $\begingroup$ OK but, if that means what I think it means, that massively changes the question. If $R$ is a general regular expression, you must use the first construction because, in that case, "other than $R$" wouldn't make sense. On the other hand, if you are just considering a single character $a$, my answer applies. $\endgroup$ Commented Oct 29, 2015 at 12:34
  • 1
    $\begingroup$ @justin I made a big edit to my answer to try to explain the bigger picture and why "other than $a$" is OK but "other than $R$" is not. Let me know if that helps. If you have follow-up questions about my edited answer, we should maybe move to chat. $\endgroup$ Commented Oct 30, 2015 at 10:58

1 Answer 1

4
$\begingroup$

Yes, the two automata are equivalent: both accept the language $a^*$.

However, if you're just interested in the language $a^*$, there's no reason to use either of those two automata. The langauge $a^*$ is accepted by the automaton that has a single state, which is the start state and is accepting. The single transition is an $a$ transition from the state to itself. If this automaton receives any number of $a$'s (including zero), it is in the accepting state; if it receives any other character, it rejects because there is no transition.

So, what is the point of the first automaton in the question? Why would you ever use a four-state NFA with $\lambda$-transitions to accept something that a one-state NFA can do? The point is that the automaton is designed to be used as a "subroutine" in an inductive translation of regular expressions to NFAs, via what are called generalized NFAs. In an ordinary NFA, every transition is labelled with a single symbol from the alphabet (or with $\lambda$, if you're allowing that kind of transition); in a generalized NFA, each transition is labelled with a regular expression. To convert the regular expression $R$ to an NFA, you start with the automaton with two states: a start state, an accepting state and a transition between them labelled $R$. You then recursively replace transitions labelled with regular expressions with automata whose transitions are labelled with simpler regular expressions.

The construction shown in the first diagram is used to replace an edge labelled $R^*$ with an automaton whose edges are labelled with the simpler regular expressions $\lambda$ and $R$. Note that $R$ is (slightly) simpler than $R^*$: it has one operation fewer.

In general, the second diagram can't be used to replace a transition labelled $R$, because "other than $R$" is shorthand for the regular expression that matches exactly the strings not matched by $R$. Since we don't usually include negation in the definition of regular expressions, this means that "other than $R$" can be some horribly long regular expression that isn't simpler than $R^*$, because it contains many more operations. This would break the recursive scheme: we're trying to make things simpler all the time but this step would make things more complicated. Trying to prove that you always get to an ordinary NFA where every transition is labelled by a single symbol (the simplest possible regular expression!) would now be very difficult.

Even if you did allow negations in your regular expressions, you wouldn't be done yet. In that case, you've removed an edge labelled $R^*$ but introduced one labelled $\neg R$. This has the same number of operations, so it isn't simpler. Again, it's going to be difficult to prove that you always end up with an ordinary NFA. Also, you're going to need to design an automaton that replaces an edge labelled $\neg R$ with ones with simpler labels.

If it's not appropriate to write "other than $R$" for a general regular expression, why is it OK to write "other than $a$"? Well, that's just a shorthand for "I'm too lazy to draw a separate transition for each symbol $b\in\Sigma\setminus\{a\}$." That's just an abbreviation, whereas writing "$\neg R$" on an edge subtly hides potentially vast complexity.

$\endgroup$
11
  • $\begingroup$ :Yeah I'm really trying to see whether we could replace the commonly used diagram to show NFA of Kleene Star(image 1) with the 2nd image that uses less transition and state. $\endgroup$
    – justin
    Commented Oct 29, 2015 at 10:18
  • $\begingroup$ For complete DFA (a requirement sometimes made) for alphabet with more than one symbol, you need the second state. $\endgroup$
    – Raphael
    Commented Oct 29, 2015 at 17:36
  • $\begingroup$ @Raphael But the question is asking for an NFA. Does anyone define NFAs in a way that requires the second state? (Genuine question; I can't remember having seen them defined that way.) $\endgroup$ Commented Oct 29, 2015 at 18:53
  • $\begingroup$ @DavidRicherby Right you are. I have no idea if there are such definitions -- probably. (Rule 34?) $\endgroup$
    – Raphael
    Commented Oct 29, 2015 at 19:41
  • $\begingroup$ @DavidRicherby:I'm not familiar with generalized NFA's.Still I think it's(G-NFA) NFA's that use regular expressions isn't it?I've read the whole answer and the thing that confuses me is about the 'complexity'.Do you mean to say that if we place 'other than R' on an edge you can't convert it into regular expressions?Should we move to chat or is there any other way to get clear about this answer? $\endgroup$
    – justin
    Commented Nov 4, 2015 at 8:48

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.