Loopless NFA equivalent in strength to NFA

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite












For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.



How do I prove this?






automata finite-automata







share|cite|improve this question









New contributor




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























    up vote
    2
    down vote

    favorite












    For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.



    How do I prove this?






    automata finite-automata







    share|cite|improve this question









    New contributor




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





















      up vote
      2
      down vote

      favorite









      up vote
      2
      down vote

      favorite











      For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.



      How do I prove this?






      automata finite-automata







      share|cite|improve this question









      New contributor




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











      For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.



      How do I prove this?






      automata finite-automata




      automata finite-automata






      share|cite|improve this question









      New contributor




      Karthik 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




      Karthik 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 23 mins ago









      Thinh D. Nguyen

      3,56611468




      3,56611468






      New contributor




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









      asked 1 hour ago









      Karthik

      111




      111




      New contributor




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





      New contributor





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






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




















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          1
          down vote













          Make two copies of your original NFA and connect them in an appropriate way.






          share|cite|improve this answer



























            up vote
            1
            down vote













            Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).



            Do not forget to set the starting node and final nodes appropriately.






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



              );






              Karthik 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%2f99472%2floopless-nfa-equivalent-in-strength-to-nfa%23new-answer', 'question_page');

              );

              Post as a guest

















              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes








              up vote
              1
              down vote













              Make two copies of your original NFA and connect them in an appropriate way.






              share|cite|improve this answer
























                up vote
                1
                down vote













                Make two copies of your original NFA and connect them in an appropriate way.






                share|cite|improve this answer






















                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  Make two copies of your original NFA and connect them in an appropriate way.






                  share|cite|improve this answer












                  Make two copies of your original NFA and connect them in an appropriate way.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 1 hour ago









                  Yuval Filmus

                  185k12176337




                  185k12176337




















                      up vote
                      1
                      down vote













                      Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).



                      Do not forget to set the starting node and final nodes appropriately.






                      share|cite|improve this answer
























                        up vote
                        1
                        down vote













                        Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).



                        Do not forget to set the starting node and final nodes appropriately.






                        share|cite|improve this answer






















                          up vote
                          1
                          down vote










                          up vote
                          1
                          down vote









                          Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).



                          Do not forget to set the starting node and final nodes appropriately.






                          share|cite|improve this answer












                          Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).



                          Do not forget to set the starting node and final nodes appropriately.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered 17 mins ago









                          Thinh D. Nguyen

                          3,56611468




                          3,56611468




















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









                               

                              draft saved


                              draft discarded


















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












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











                              Karthik 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%2f99472%2floopless-nfa-equivalent-in-strength-to-nfa%23new-answer', 'question_page');

                              );

                              Post as a guest
































































                              Comments

                              Post a Comment

                              Popular posts from this blog

                              White Anglo-Saxon Protestant

                              Image
                              White Anglo-Saxon Protestants ( WASPs ) are a social group of wealthy and well-connected white Americans, of Protestant and predominantly British ancestry, who trace their ancestry to the American colonial period. Until at least the 1960s, this group has dominated American society and culture and dominated in the leadership of the Whig and Republican parties. They usually are very well placed in major financial, business, legal and academic institutions and had close to a monopoly of elite society due to intermarriage and nepotism. [1] During the latter half of the twentieth century, outsider ethnic and racial groups grew in influence and WASP dominance weakened. Americans are increasingly criticizing the WASP hegemony and disparaging WASPs as the epitome of "the Establishment". The Random House Unabridged Dictionary (1998) says the term is "Sometimes Disparaging and Offensive". [2] [3] The term WASP is often used as a pejorative to classify their historical dom...
                              Read more

                              BuddyTV

                              BuddyTV Owner David Niu, Andy Liu Created by Various contributors Website www.buddytv.com Launched July 31, 2007 Current status Offline BuddyTV was an entertainment-based website based in Seattle, Washington, which generated content about television programs and sporting events. The website published information about celebrity and related entertainment news through a series of articles, entertainment profiles, actor biographies and user forums. [1] On 31 December 2014, Smart TV manufacturer VIZIO acquired BuddyTV's parent Advanced Media Research Group, Inc., in order to expand content and service offerings. [2] The site was shut down on 22 May 2018. [3] Contents 1 History 2 Business model 3 Impact 4 See also 5 References 6 External links History BuddyTV was co-founded in 2005 by Andy Liu and David Niu. The pair graduated from the University of Pennsylvania with a Master of Business Administration. They sold their previous company, NetConversions, to aQuantive in 2004...
                              Read more

                              Conflict (narrative)

                              Image
                              Conflict in narrative comes in many forms. "Man versus man", such as is depicted here in the battle between King Arthur and Mordred, is particularly common in traditional literature, fairy tales and myths. [1] In works of narrative, conflict is the challenge main characters need to solve to achieve their goals. Traditionally, conflict is a major literary element that creates challenges in a story by adding uncertainty to if the goal would be achieved. A narrative is not limited to a single conflict. While conflicts may not always resolve in narrative, the resolution of a conflict creates closure or fulfillment, which may or may not occur at a story's end. Contents 1 Basic nature 2 Classification 2.1 Man against man 2.2 Man against nature 2.3 Man against self 2.4 Man against society 3 History 4 See also 5 References 6 External links Basic nature Conflict in literature refers to the different drives of the characters or forces involved. Conflict may be internal o...
                              Read more