PDA: Symbol in first half











up vote
1
down vote

favorite
1












How do I construct a PDA where:



$L = {w in {0, 1} ∗ : |w| text{ is even and } w text{ contains at least one 1-Symbol in the first Half}}$



To me it seems impossible to know when I reached the midpoint.










share|cite|improve this question









New contributor




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




















  • Parallelly, try also the pumping lemma.
    – Berci
    Nov 21 at 17:34










  • The assignment doesn't say that the PDA needs to be deterministic.
    – rici
    Nov 21 at 19:11










  • ...although a DPDA does exist, too.
    – rici
    Nov 21 at 21:13






  • 1




    Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
    – Peter Leupold
    2 days ago










  • figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
    – ZerataX
    2 days ago















up vote
1
down vote

favorite
1












How do I construct a PDA where:



$L = {w in {0, 1} ∗ : |w| text{ is even and } w text{ contains at least one 1-Symbol in the first Half}}$



To me it seems impossible to know when I reached the midpoint.










share|cite|improve this question









New contributor




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




















  • Parallelly, try also the pumping lemma.
    – Berci
    Nov 21 at 17:34










  • The assignment doesn't say that the PDA needs to be deterministic.
    – rici
    Nov 21 at 19:11










  • ...although a DPDA does exist, too.
    – rici
    Nov 21 at 21:13






  • 1




    Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
    – Peter Leupold
    2 days ago










  • figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
    – ZerataX
    2 days ago













up vote
1
down vote

favorite
1









up vote
1
down vote

favorite
1






1





How do I construct a PDA where:



$L = {w in {0, 1} ∗ : |w| text{ is even and } w text{ contains at least one 1-Symbol in the first Half}}$



To me it seems impossible to know when I reached the midpoint.










share|cite|improve this question









New contributor




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











How do I construct a PDA where:



$L = {w in {0, 1} ∗ : |w| text{ is even and } w text{ contains at least one 1-Symbol in the first Half}}$



To me it seems impossible to know when I reached the midpoint.







computer-science formal-languages automata






share|cite|improve this question









New contributor




ZerataX 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




ZerataX 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 Nov 22 at 2:45





















New contributor




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









asked Nov 21 at 17:19









ZerataX

164




164




New contributor




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





New contributor





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






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












  • Parallelly, try also the pumping lemma.
    – Berci
    Nov 21 at 17:34










  • The assignment doesn't say that the PDA needs to be deterministic.
    – rici
    Nov 21 at 19:11










  • ...although a DPDA does exist, too.
    – rici
    Nov 21 at 21:13






  • 1




    Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
    – Peter Leupold
    2 days ago










  • figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
    – ZerataX
    2 days ago


















  • Parallelly, try also the pumping lemma.
    – Berci
    Nov 21 at 17:34










  • The assignment doesn't say that the PDA needs to be deterministic.
    – rici
    Nov 21 at 19:11










  • ...although a DPDA does exist, too.
    – rici
    Nov 21 at 21:13






  • 1




    Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
    – Peter Leupold
    2 days ago










  • figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
    – ZerataX
    2 days ago
















Parallelly, try also the pumping lemma.
– Berci
Nov 21 at 17:34




Parallelly, try also the pumping lemma.
– Berci
Nov 21 at 17:34












The assignment doesn't say that the PDA needs to be deterministic.
– rici
Nov 21 at 19:11




The assignment doesn't say that the PDA needs to be deterministic.
– rici
Nov 21 at 19:11












...although a DPDA does exist, too.
– rici
Nov 21 at 21:13




...although a DPDA does exist, too.
– rici
Nov 21 at 21:13




1




1




Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
– Peter Leupold
2 days ago




Maybe it helps to reformulate the set definition. Equivalently we could say: $|w|$ is even, $w$ contains at least one 1-symbol, and the first 1-symbol that occurs is in the first half of $w$.
– Peter Leupold
2 days ago












figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
– ZerataX
2 days ago




figured it out yesterday by myself, but @PeterLeupold reformulation really helps a lot. thanks!
– ZerataX
2 days ago










1 Answer
1






active

oldest

votes

















up vote
1
down vote



accepted










So this is my solution:
PDA



I just stack 1s until I find the first 1-Symbol, then I pop them to see if the first 1 was in the first or second half and then I just make sure that the word is even.






share|cite|improve this answer










New contributor




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


















    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: "69"
    };
    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: 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
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    ZerataX 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%2fmath.stackexchange.com%2fquestions%2f3008055%2fpda-symbol-in-first-half%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








    up vote
    1
    down vote



    accepted










    So this is my solution:
    PDA



    I just stack 1s until I find the first 1-Symbol, then I pop them to see if the first 1 was in the first or second half and then I just make sure that the word is even.






    share|cite|improve this answer










    New contributor




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






















      up vote
      1
      down vote



      accepted










      So this is my solution:
      PDA



      I just stack 1s until I find the first 1-Symbol, then I pop them to see if the first 1 was in the first or second half and then I just make sure that the word is even.






      share|cite|improve this answer










      New contributor




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




















        up vote
        1
        down vote



        accepted







        up vote
        1
        down vote



        accepted






        So this is my solution:
        PDA



        I just stack 1s until I find the first 1-Symbol, then I pop them to see if the first 1 was in the first or second half and then I just make sure that the word is even.






        share|cite|improve this answer










        New contributor




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









        So this is my solution:
        PDA



        I just stack 1s until I find the first 1-Symbol, then I pop them to see if the first 1 was in the first or second half and then I just make sure that the word is even.







        share|cite|improve this answer










        New contributor




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



        share|cite|improve this answer








        edited yesterday





















        New contributor




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









        answered 2 days ago









        ZerataX

        164




        164




        New contributor




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





        New contributor





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






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






















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










             

            draft saved


            draft discarded


















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













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












            ZerataX 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%2fmath.stackexchange.com%2fquestions%2f3008055%2fpda-symbol-in-first-half%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

            Berounka

            Sphinx de Gizeh

            Different font size/position of beamer's navigation symbols template's content depending on regular/plain...