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.










share|cite|improve this question









New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • 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















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.










share|cite|improve this question









New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • 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













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.










share|cite|improve this question









New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











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






share|cite|improve this question









New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited yesterday









Raphael

57.1k23139311




57.1k23139311






New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked yesterday









Tom

203




203




New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • 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










  • 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










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






share|cite|improve this answer























  • 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




















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.






share|cite|improve this answer























    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',
    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
    });


    }
    });






    Tom is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    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








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






    share|cite|improve this answer























    • 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

















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






    share|cite|improve this answer























    • 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















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






    share|cite|improve this answer














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







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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




















    • 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












    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.






    share|cite|improve this answer



























      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.






      share|cite|improve this answer

























        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.






        share|cite|improve this answer














        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.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited yesterday

























        answered yesterday









        Mr. Sigma.

        343116




        343116






















            Tom is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Quarter-circle Tiles

            build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

            Mont Emei