Language of all strings that has exactly 1 triple b
up vote
2
down vote
favorite
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
New contributor
add a comment |
up vote
2
down vote
favorite
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
New contributor
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
yesterday
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
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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
New contributor
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
New contributor
New contributor
edited yesterday
Raphael♦
57.1k23139311
57.1k23139311
New contributor
asked yesterday
Tom
203
203
New contributor
New contributor
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
yesterday
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
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday
add a comment |
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
yesterday
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
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
yesterday
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
yesterday
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
yesterday
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
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
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^*$.
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
add a comment |
up vote
4
down vote
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.
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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^*$.
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
add a comment |
up vote
2
down vote
accepted
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^*$.
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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^*$.
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^*$.
edited yesterday
answered yesterday
Apass.Jack
4,9311429
4,9311429
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
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
yesterday
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
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
this won't generate bbb
– Mr. Sigma.
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
yesterday
Now, both solutions are correct?
– Tom
yesterday
Now, both solutions are correct?
– Tom
yesterday
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
yesterday
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
yesterday
add a comment |
up vote
4
down vote
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.
add a comment |
up vote
4
down vote
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.
add a comment |
up vote
4
down vote
up vote
4
down vote
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.
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.
edited yesterday
answered yesterday
Mr. Sigma.
343116
343116
add a comment |
add a comment |
Tom is a new contributor. Be nice, and check out our Code of Conduct.
Tom is a new contributor. Be nice, and check out our Code of Conduct.
Tom is a new contributor. Be nice, and check out our Code of Conduct.
Tom is a new contributor. Be nice, and check out our Code of Conduct.
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.
yesterday
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
yesterday
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
yesterday