Language of all strings that has exactly 1 triple b
Clash Royale CLAN TAG#URR8PPP
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
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
asked Dec 2 at 10:07
Tom
203
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
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
asked Dec 2 at 10:07
Tom
203
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 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 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45
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
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
asked Dec 2 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 at 11:42
Raphael♦
57.2k23139311
asked Dec 2 at 10:07
Tom
203
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
asked Dec 2 at 10:07
Tom
203
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
edited Dec 2 at 11:42
Raphael♦
57.2k23139311
57.2k23139311
asked Dec 2 at 10:07
Tom
203
asked Dec 2 at 10:07
Tom
203
asked Dec 2 at 10:07
Tom
203
203
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 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 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45
add a comment |
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 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 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 at 11:14
Perhaps you can convert FM of that into a regular expression.
– Mr. Sigma.
Dec 2 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 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 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45
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^*$.
answered Dec 2 at 11:50
Apass.Jack
5,5781531
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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 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 at 12:25
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.
answered Dec 2 at 11:37
Mr. Sigma.
522320
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^*$.
answered Dec 2 at 11:50
Apass.Jack
5,5781531
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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 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 at 12:25
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^*$.
answered Dec 2 at 11:50
Apass.Jack
5,5781531
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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 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 at 12:25
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^*$.
answered Dec 2 at 11:50
Apass.Jack
5,5781531
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 at 11:50
Apass.Jack
5,5781531
edited Dec 2 at 12:03
answered Dec 2 at 11:50
Apass.Jack
5,5781531
answered Dec 2 at 11:50
Apass.Jack
5,5781531
answered Dec 2 at 11:50
Apass.Jack
5,5781531
5,5781531
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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 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 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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 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 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 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 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
this won't generate bbb
– Mr. Sigma.
Dec 2 at 12:00
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Corrected. The symmetry is, in fact, useful in understanding and verification.
– Apass.Jack
Dec 2 at 12:10
Now, both solutions are correct?
– Tom
Dec 2 at 12:21
Now, both solutions are correct?
– Tom
Dec 2 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 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 at 12:25
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.
answered Dec 2 at 11:37
Mr. Sigma.
522320
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.
answered Dec 2 at 11:37
Mr. Sigma.
522320
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.
answered Dec 2 at 11:37
Mr. Sigma.
522320
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 at 11:37
Mr. Sigma.
522320
edited Dec 2 at 12:41
answered Dec 2 at 11:37
Mr. Sigma.
522320
answered Dec 2 at 11:37
Mr. Sigma.
522320
answered Dec 2 at 11:37
Mr. Sigma.
522320
522320
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 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 at 11:17
Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$
– chi
Dec 2 at 11:45