Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?












2














I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:



If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?



Now, A is no longer recursive.



This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:



'if (x=1)
{return true}'



For TM(A), A is accepted.



Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.





Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.



However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.



To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?



If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?



Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?



If I've missed the point entirely or have been unclear, please do let me know.










share|cite|improve this question





























    2














    I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:



    If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?



    Now, A is no longer recursive.



    This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:



    'if (x=1)
    {return true}'



    For TM(A), A is accepted.



    Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.





    Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.



    However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.



    To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?



    If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?



    Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?



    If I've missed the point entirely or have been unclear, please do let me know.










    share|cite|improve this question



























      2












      2








      2







      I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:



      If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?



      Now, A is no longer recursive.



      This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:



      'if (x=1)
      {return true}'



      For TM(A), A is accepted.



      Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.





      Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.



      However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.



      To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?



      If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?



      Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?



      If I've missed the point entirely or have been unclear, please do let me know.










      share|cite|improve this question















      I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:



      If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?



      Now, A is no longer recursive.



      This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:



      'if (x=1)
      {return true}'



      For TM(A), A is accepted.



      Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.





      Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.



      However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.



      To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?



      If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?



      Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?



      If I've missed the point entirely or have been unclear, please do let me know.







      formal-languages turing-machines finite-automata formal-grammars chomsky-hierarchy






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited yesterday









      psmears

      45135




      45135










      asked 2 days ago









      TheRealPaulMcCartneyTheRealPaulMcCartney

      255




      255






















          2 Answers
          2






          active

          oldest

          votes


















          5














          A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.



          However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*





          Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.





          As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.



          (*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability






          share|cite|improve this answer





















          • Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
            – TheRealPaulMcCartney
            2 days ago












          • The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
            – kutschkem
            yesterday



















          4















          a language A that is recursive for some Turing Machine




          That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.






          share|cite|improve this answer





















          • Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
            – David Richerby
            2 days ago












          • Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
            – TheRealPaulMcCartney
            2 days ago











          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%2f102565%2fcan-a-formal-language-be-of-a-type-re-rec-regular-etc-for-one-tm-but-of-a%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









          5














          A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.



          However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*





          Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.





          As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.



          (*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability






          share|cite|improve this answer





















          • Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
            – TheRealPaulMcCartney
            2 days ago












          • The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
            – kutschkem
            yesterday
















          5














          A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.



          However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*





          Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.





          As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.



          (*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability






          share|cite|improve this answer





















          • Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
            – TheRealPaulMcCartney
            2 days ago












          • The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
            – kutschkem
            yesterday














          5












          5








          5






          A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.



          However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*





          Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.





          As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.



          (*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability






          share|cite|improve this answer












          A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.



          However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*





          Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.





          As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.



          (*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 days ago









          wazdrawazdra

          1956




          1956












          • Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
            – TheRealPaulMcCartney
            2 days ago












          • The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
            – kutschkem
            yesterday


















          • Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
            – TheRealPaulMcCartney
            2 days ago












          • The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
            – kutschkem
            yesterday
















          Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
          – TheRealPaulMcCartney
          2 days ago






          Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks!
          – TheRealPaulMcCartney
          2 days ago














          The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
          – TheRealPaulMcCartney
          2 days ago




          The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above?
          – TheRealPaulMcCartney
          2 days ago












          @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
          – kutschkem
          yesterday




          @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example).
          – kutschkem
          yesterday











          4















          a language A that is recursive for some Turing Machine




          That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.






          share|cite|improve this answer





















          • Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
            – David Richerby
            2 days ago












          • Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
            – TheRealPaulMcCartney
            2 days ago
















          4















          a language A that is recursive for some Turing Machine




          That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.






          share|cite|improve this answer





















          • Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
            – David Richerby
            2 days ago












          • Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
            – TheRealPaulMcCartney
            2 days ago














          4












          4








          4







          a language A that is recursive for some Turing Machine




          That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.






          share|cite|improve this answer













          a language A that is recursive for some Turing Machine




          That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 days ago









          David RicherbyDavid Richerby

          66.2k15100190




          66.2k15100190












          • Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
            – David Richerby
            2 days ago












          • Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
            – TheRealPaulMcCartney
            2 days ago


















          • Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
            – TheRealPaulMcCartney
            2 days ago










          • @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
            – David Richerby
            2 days ago












          • Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
            – TheRealPaulMcCartney
            2 days ago
















          Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
          – TheRealPaulMcCartney
          2 days ago




          Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"?
          – TheRealPaulMcCartney
          2 days ago












          @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
          – David Richerby
          2 days ago






          @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.)
          – David Richerby
          2 days ago














          Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
          – TheRealPaulMcCartney
          2 days ago




          Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much!
          – TheRealPaulMcCartney
          2 days ago


















          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.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102565%2fcan-a-formal-language-be-of-a-type-re-rec-regular-etc-for-one-tm-but-of-a%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

          1300-talet

          1300-talet

          Display a custom attribute below product name in the front-end Magento 1.9.3.8