Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.
Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.
automata finite-automata regular-expressions
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
add a comment |
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.
Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.
automata finite-automata regular-expressions
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45
add a comment |
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.
Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.
automata finite-automata regular-expressions
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.
Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.
automata finite-automata regular-expressions
automata finite-automata regular-expressions
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
edited Dec 2 '18 at 11:42
Raphael♦
57.3k23139312
57.3k23139312
asked Dec 2 '18 at 10:07
Tom
203
asked Dec 2 '18 at 10:07
Tom
203
asked Dec 2 '18 at 10:07
Tom
203
203
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45
add a comment |
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45
add a comment |
2 Answers
2
active
oldest
votes
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.
What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.
That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^*((bmid bb)aa^*)^*$.
So, a regular expression could be $a^*((bmid bb)aa^*)^*bbb(aa^*(bmid bb))^*a^*$, or written symmetrically, $a^*((bmid bb)aa^*)^*bbb(a^*a(bbmid b))^*a^*$.
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
add a comment |
It seems you are almost there. You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$
Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
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%2fcs.stackexchange.com%2fquestions%2f100866%2flanguage-of-all-strings-that-has-exactly-1-triple-b%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.
What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.
That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^*((bmid bb)aa^*)^*$.
So, a regular expression could be $a^*((bmid bb)aa^*)^*bbb(aa^*(bmid bb))^*a^*$, or written symmetrically, $a^*((bmid bb)aa^*)^*bbb(a^*a(bbmid b))^*a^*$.
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
add a comment |
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.
What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.
That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^*((bmid bb)aa^*)^*$.
So, a regular expression could be $a^*((bmid bb)aa^*)^*bbb(aa^*(bmid bb))^*a^*$, or written symmetrically, $a^*((bmid bb)aa^*)^*bbb(a^*a(bbmid b))^*a^*$.
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
add a comment |
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.
What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.
That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^*((bmid bb)aa^*)^*$.
So, a regular expression could be $a^*((bmid bb)aa^*)^*bbb(aa^*(bmid bb))^*a^*$, or written symmetrically, $a^*((bmid bb)aa^*)^*bbb(a^*a(bbmid b))^*a^*$.
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.
What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.
That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^*((bmid bb)aa^*)^*$.
So, a regular expression could be $a^*((bmid bb)aa^*)^*bbb(aa^*(bmid bb))^*a^*$, or written symmetrically, $a^*((bmid bb)aa^*)^*bbb(a^*a(bbmid b))^*a^*$.
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
edited Dec 2 '18 at 12:03
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
answered Dec 2 '18 at 11:50
Apass.Jack
7,2291633
7,2291633
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
add a comment |
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right?
– Tom
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 '18 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 '18 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Now, both solutions are correct?
– Tom
Dec 2 '18 at 12:21
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$.
– Apass.Jack
Dec 2 '18 at 12:25
add a comment |
It seems you are almost there. You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$
Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
add a comment |
It seems you are almost there. You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$
Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
add a comment |
It seems you are almost there. You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$
Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
It seems you are almost there. You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$
Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
edited Dec 2 '18 at 12:41
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
answered Dec 2 '18 at 11:37
Mr. Sigma.
556322
556322
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fcs.stackexchange.com%2fquestions%2f100866%2flanguage-of-all-strings-that-has-exactly-1-triple-b%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
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 '18 at 11:14
I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas??
– Tom
Dec 2 '18 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 '18 at 11:45