Language of all strings that has exactly 1 triple b












2














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
























  • 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
















2














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
























  • 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














2












2








2







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















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















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 2 '18 at 11:42









Raphael

57.3k23139312




57.3k23139312










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


















  • 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










2 Answers
2






active

oldest

votes


















2














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
    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





















4














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


    }
    });














    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









    2














    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
      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


















    2














    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
      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
















    2












    2








    2






    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 Dec 2 '18 at 12:03

























    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




















    • 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













    4














    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




























      4














      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


























        4












        4








        4






        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 Dec 2 '18 at 12:41

























        answered Dec 2 '18 at 11:37









        Mr. Sigma.

        556322




        556322






























            draft saved

            draft discarded




















































            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

            Wiesbaden

            Marschland

            Dieringhausen