1

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and a*+b. To us they seem functionally equivalent.

On the left is the nfa produced by a*b and on the right a*+b. Can you basically drop the + sign?

enter image description here

KDecker
  • 861
  • 2
  • 11
  • 23
  • Yes, to me as well, they seem the same. – Berci Oct 14 '14 at 20:42
  • 1
    The right one does not produce $a^\ast + b$. Note that every accepted word of the right automaton has to end in $b$, but $a^\ast + b$ would also allow $a$ for example (and even the empty word). – PhoemueX Oct 14 '14 at 20:49
  • 1
    @PhoemueX It believe that the "plus" sign in this case stands for Kleene plus, rather than "or". If this is the case, the combination of "star-plus" is indeed the same as "star". – Peter Košinár Oct 14 '14 at 22:00
  • This is where we were stuck, and still are. But I think the issue we face is with the comment above. We looked at the wikipedia page for regex, it says that + represents "one or more of the preceding character". But after using that definition to rework problems we had solutions to we realized it didn't make sense. // So it seems that there is sometimes a different meaning to + at different times. How can you tell what is meant? – KDecker Oct 14 '14 at 23:04

1 Answers1

1

In regular expressions there can be two meanings for the '+'.

First, it can be the 'Kleene' '+' that stands for several times and at least once. But when this is the case its superscript: For example $a^+$ stands for $\{a^n|n\geq 1\}$.

Otherwise it can stand for 'or'. in that case it's not superscript. For example $a+b$ stand for either $a$ or $b$.

For your example I think that the second expression is $a^*+b$ and is thus different to $a^*b$. the interpretation you gave was ${a^*}^+b$ for which you gave the automaton and which is equivalent to $a^*b$.

wece
  • 2,732