Difference between a*b and a*+b? Does the "+" denote Kleene plus or "or"?

5.1k Views Asked by At

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

1

There are 1 best solutions below

0
On

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$.