REGEX L(r) = {a^n b^m : n + m is even}, r =?












0














So I did a problem earlier that said:



L(r) = {w in {a,b}* : w contains at least 2 a's}


For that one I said {a^2n , b} because that guarantees a string like aab or aabaab etc. Not sure how to approach the one I posted about in the title. Possibly a solution might be a^2n, b^2m so its always even, but also 2 odd numbers like a^n b^3m is also always even. Am i allowed to set boundaries like n>=m?



Thank you!






regex math automata formal-languages computability







share|improve this question




















  • 1




    Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
    – Corion
    Nov 13 '18 at 10:02






  • 1




    what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
    – Nahuel Fouilleul
    Nov 13 '18 at 10:31












  • @Corion how would I write that in terms of r? I understand the logic just not the syntax.
    – solnay
    Nov 13 '18 at 10:39






  • 2




    I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
    – Asunez
    Nov 13 '18 at 10:45






  • 1




    @Asunez As I showed, the language is regular, as it can be accepted by a DFA.
    – Corion
    Nov 13 '18 at 10:48
















0














So I did a problem earlier that said:



L(r) = {w in {a,b}* : w contains at least 2 a's}


For that one I said {a^2n , b} because that guarantees a string like aab or aabaab etc. Not sure how to approach the one I posted about in the title. Possibly a solution might be a^2n, b^2m so its always even, but also 2 odd numbers like a^n b^3m is also always even. Am i allowed to set boundaries like n>=m?



Thank you!






regex math automata formal-languages computability







share|improve this question




















  • 1




    Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
    – Corion
    Nov 13 '18 at 10:02






  • 1




    what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
    – Nahuel Fouilleul
    Nov 13 '18 at 10:31












  • @Corion how would I write that in terms of r? I understand the logic just not the syntax.
    – solnay
    Nov 13 '18 at 10:39






  • 2




    I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
    – Asunez
    Nov 13 '18 at 10:45






  • 1




    @Asunez As I showed, the language is regular, as it can be accepted by a DFA.
    – Corion
    Nov 13 '18 at 10:48














0












0








0







So I did a problem earlier that said:



L(r) = {w in {a,b}* : w contains at least 2 a's}


For that one I said {a^2n , b} because that guarantees a string like aab or aabaab etc. Not sure how to approach the one I posted about in the title. Possibly a solution might be a^2n, b^2m so its always even, but also 2 odd numbers like a^n b^3m is also always even. Am i allowed to set boundaries like n>=m?



Thank you!






regex math automata formal-languages computability







share|improve this question















So I did a problem earlier that said:



L(r) = {w in {a,b}* : w contains at least 2 a's}


For that one I said {a^2n , b} because that guarantees a string like aab or aabaab etc. Not sure how to approach the one I posted about in the title. Possibly a solution might be a^2n, b^2m so its always even, but also 2 odd numbers like a^n b^3m is also always even. Am i allowed to set boundaries like n>=m?



Thank you!






regex math automata formal-languages computability




regex math automata formal-languages computability






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 13 '18 at 10:27









mrzasa

8,973103878




8,973103878










asked Nov 13 '18 at 9:37









solnaysolnay

134




134








  • 1




    Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
    – Corion
    Nov 13 '18 at 10:02






  • 1




    what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
    – Nahuel Fouilleul
    Nov 13 '18 at 10:31












  • @Corion how would I write that in terms of r? I understand the logic just not the syntax.
    – solnay
    Nov 13 '18 at 10:39






  • 2




    I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
    – Asunez
    Nov 13 '18 at 10:45






  • 1




    @Asunez As I showed, the language is regular, as it can be accepted by a DFA.
    – Corion
    Nov 13 '18 at 10:48














  • 1




    Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
    – Corion
    Nov 13 '18 at 10:02






  • 1




    what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
    – Nahuel Fouilleul
    Nov 13 '18 at 10:31












  • @Corion how would I write that in terms of r? I understand the logic just not the syntax.
    – solnay
    Nov 13 '18 at 10:39






  • 2




    I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
    – Asunez
    Nov 13 '18 at 10:45






  • 1




    @Asunez As I showed, the language is regular, as it can be accepted by a DFA.
    – Corion
    Nov 13 '18 at 10:48








1




1




Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
– Corion
Nov 13 '18 at 10:02




Consider the automaton which accepts a^n when n is even. The "failure" case would be that n is odd. In that "failure" case, you want a following automaton b^m which accepts when m is odd. Otherwise, you want a following automaton b^m which accepts when m is even.
– Corion
Nov 13 '18 at 10:02




1




1




what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
– Nahuel Fouilleul
Nov 13 '18 at 10:31






what about ^(?=(?:..)*$)[ab]*$ (regex101.com/r/1aldWm/1)
– Nahuel Fouilleul
Nov 13 '18 at 10:31














@Corion how would I write that in terms of r? I understand the logic just not the syntax.
– solnay
Nov 13 '18 at 10:39




@Corion how would I write that in terms of r? I understand the logic just not the syntax.
– solnay
Nov 13 '18 at 10:39




2




2




I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
– Asunez
Nov 13 '18 at 10:45




I think this question better suits Mathematics StackExchange site and it's regular-expressions tag. Also, are you sure there is a possibility to use a regular expression for this? Seems more like a grammar is to be used here, since irregularities you mention oppose the "regular" part in "regex" :)
– Asunez
Nov 13 '18 at 10:45




1




1




@Asunez As I showed, the language is regular, as it can be accepted by a DFA.
– Corion
Nov 13 '18 at 10:48




@Asunez As I showed, the language is regular, as it can be accepted by a DFA.
– Corion
Nov 13 '18 at 10:48












1 Answer
1






active

oldest

votes


















1














You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.



A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.



Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)






share|improve this answer























    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    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: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    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%2fstackoverflow.com%2fquestions%2f53277926%2fregex-lr-an-bm-n-m-is-even-r%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1














    You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.



    A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.



    Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)






    share|improve this answer




























      1














      You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.



      A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.



      Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)






      share|improve this answer


























        1












        1








        1






        You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.



        A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.



        Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)






        share|improve this answer














        You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.



        A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.



        Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Nov 13 '18 at 17:12

























        answered Nov 13 '18 at 17:06









        ricirici

        152k19132197




        152k19132197






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


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





            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%2fstackoverflow.com%2fquestions%2f53277926%2fregex-lr-an-bm-n-m-is-even-r%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

            List item for chat from Array inside array React Native

            Image
            0 This is my code for Chat Box, the window where I have "In" and "Out" messages are appearing. import React, { Component } from "react"; import { StyleSheet, Text, View, TouchableOpacity, TextInput, FlatList, Platform, AsyncStorage } from "react-native"; import Tutor from "../image/krutika.jpg"; import { Container, Header, Left, Input, Body, Right, Thumbnail, Button } from "native-base"; import FontAwesome from "react-native-vector-icons/FontAwesome"; import Ionicons from "react-native-vector-icons/Ionicons"; import Icon1 from "react-native-vector-icons/FontAwesome"; import axios from "axios"; export default class ChatBox extends Component { st...
            Read more

            Thiostrepton

            Image
            Thiostrepton [1] Names Other names Alaninamide, Bryamycin, Thiactin Identifiers CAS Number 1393-48-2   Y 3D model (JSmol) Interactive image ChEMBL ChEMBL468719   N ECHA InfoCard 100.014.304 PubChem CID 16130278 InChI InChI=1S/C72H85N19O18S5/c1-14-26(3)47-63(105)78-30(7)57(99)75-28(5)56(98)76-31(8)58(100)91-72-19-18-40(66-85-43(22-111-66)59(101)77-29(6)55(97)74-27(4)54(73)96)81-52(72)42-21-112-67(83-42)49(34(11)109-69(107)41-20-37(32(9)92)36-16-17-39(79-47)51(95)50(36)80-41)89-60(102)44-24-113-68(86-44)53(71(13,108)35(12)94)90-62(104)45-23-110-65(84-45)38(15-2)82-64(106)48(33(10)93)88-61(103)46-25-114-70(72)87-46/h15-17,20-22,24-26,30-35,39,45,47-49,51-53,79,92-95,108H,4-6,14,18-19,23H2,1-3,7-13H3,(H2,73,96)(H,74,97)(H,75,99)(H,76,98)(H,77,101)(H,78,105)(H,82,106)(H,88,103)(H,89,102)(H,90,104)(H,91,100)/b38-15-/t26-,30-,31-,32-,33+,34+,35+,39+,45+,47-,48-,49-,51-,52+,53+,71+,72+/m0/s1 Key: NSFFHOGKXHRQEW-AIHSUZKVSA-N ...
            Read more

            Caerphilly

            Image
            This article is about the town of Caerphilly. For the cheese of the same name, see Caerphilly cheese. For other uses, see Caerphilly (disambiguation). Caerphilly Welsh: Caerffili Caerphilly Castle Caerphilly Location within Caerphilly Population 30,388  OS grid reference ST1586 Principal area Caerphilly Ceremonial county Gwent Country Wales Sovereign state United Kingdom Post town CAERPHILLY Postcode district CF83 Dialling code 029 Police Gwent Fire South Wales Ambulance Welsh EU Parliament Wales UK Parliament Caerphilly Welsh Assembly Caerphilly List of places UK Wales Caerphilly 51°34′41″N 3°13′05″W  /  51.578°N 3.218°W  / 51.578; -3.218 Coordinates: 51°34′41″N 3°13′05″W  /  51.578°N 3.218°W  / 51.578; -3.218 Caerphilly ( / k aɪər ˈ f ɪ l i / ; Welsh: Caerffili , Welsh pronunciation:  [ˌkɑːɨrˈfɪlɪ] ) is a town and community in South Wales, at the southern end of the Rhymney Valley....
            Read more