Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?
$begingroup$
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?
automata
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
$endgroup$
add a comment |
$begingroup$
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?
automata
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
$endgroup$
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
1
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
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?
$endgroup$
– KDecker
Oct 14 '14 at 23:04
add a comment |
$begingroup$
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?
automata
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
$endgroup$
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?
automata
automata
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
edited Oct 14 '14 at 23:07
KDecker
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
asked Oct 14 '14 at 20:35
KDeckerKDecker
3821616
3821616
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
1
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
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?
$endgroup$
– KDecker
Oct 14 '14 at 23:04
add a comment |
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
1
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
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?
$endgroup$
– KDecker
Oct 14 '14 at 23:04
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
1
1
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
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?$endgroup$
– KDecker
Oct 14 '14 at 23:04
$begingroup$
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?$endgroup$
– KDecker
Oct 14 '14 at 23:04
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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|ngeq 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$.
answered Apr 30 '15 at 14:54
wecewece
2,3721923
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f973892%2fdifference-between-ab-and-ab-does-the-denote-kleene-plus-or-or%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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|ngeq 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$.
answered Apr 30 '15 at 14:54
wecewece
2,3721923
$endgroup$
add a comment |
$begingroup$
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|ngeq 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$.
answered Apr 30 '15 at 14:54
wecewece
2,3721923
$endgroup$
add a comment |
$begingroup$
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|ngeq 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$.
answered Apr 30 '15 at 14:54
wecewece
2,3721923
$endgroup$
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|ngeq 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$.
answered Apr 30 '15 at 14:54
wecewece
2,3721923
answered Apr 30 '15 at 14:54
wecewece
2,3721923
answered Apr 30 '15 at 14:54
wecewece
2,3721923
answered Apr 30 '15 at 14:54
wecewece
2,3721923
2,3721923
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f973892%2fdifference-between-ab-and-ab-does-the-denote-kleene-plus-or-or%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Yes, to me as well, they seem the same.
$endgroup$
– Berci
Oct 14 '14 at 20:42
$begingroup$
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).
$endgroup$
– PhoemueX
Oct 14 '14 at 20:49
1
$begingroup$
@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".
$endgroup$
– Peter Košinár
Oct 14 '14 at 22:00
$begingroup$
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?$endgroup$
– KDecker
Oct 14 '14 at 23:04