Languages that we cannot (dis)prove to be Context-FreeBase-k representations of the co-domain of a polynomial - is it context-free?For a language to be programmable, is it mandatory that it be based on a context free grammarSufficient conditions for the regularity of a context-free languageDoes there exist an extension of regular expressions that captures the context free languages?Are deterministic context-free languages closed under outfix (or other erasing operations)Is SAT a context-free language?Is equivalence of unambiguous context-free languages decidable?Example of context-free tree language which can not be generated by monadic CFTGNumber of words of length n in a context-free languageFor which $R$ is $0^a10^b10^cmid R(a,b,c)$ context-free?Continuous mathematics and formal language theory

How do I deal with an unproductive colleague in a small company?

NMaximize is not converging to a solution

Is it unprofessional to ask if a job posting on GlassDoor is real?

High voltage LED indicator 40-1000 VDC without additional power supply

Do infinite dimensional systems make sense?

Add text to same line using sed

Unable to deploy metadata from Partner Developer scratch org because of extra fields

What are these boxed doors outside store fronts in New York?

Are astronomers waiting to see something in an image from a gravitational lens that they've already seen in an adjacent image?

Arrow those variables!

How old can references or sources in a thesis be?

How much of data wrangling is a data scientist's job?

How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?

Paid for article while in US on F-1 visa?

DC-DC converter from low voltage at high current, to high voltage at low current

How does quantile regression compare to logistic regression with the variable split at the quantile?

Approximately how much travel time was saved by the opening of the Suez Canal in 1869?

Does an object always see its latest internal state irrespective of thread?

Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?

Is it legal for company to use my work email to pretend I still work there?

I'm flying to France today and my passport expires in less than 2 months

Could an aircraft fly or hover using only jets of compressed air?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

What's the output of a record needle playing an out-of-speed record



Languages that we cannot (dis)prove to be Context-Free


Base-k representations of the co-domain of a polynomial - is it context-free?For a language to be programmable, is it mandatory that it be based on a context free grammarSufficient conditions for the regularity of a context-free languageDoes there exist an extension of regular expressions that captures the context free languages?Are deterministic context-free languages closed under outfix (or other erasing operations)Is SAT a context-free language?Is equivalence of unambiguous context-free languages decidable?Example of context-free tree language which can not be generated by monadic CFTGNumber of words of length n in a context-free languageFor which $R$ is $0^a10^b10^cmid R(a,b,c)$ context-free?Continuous mathematics and formal language theory













11












$begingroup$


I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




Is there a recent survey on the subject or an open problem section from a recent conference ?



Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




The examples I found are:



  • the well known language of Primitive words $Q = > 1) $ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

  • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)

Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_Goldbach = 1^2n mid 2n$ cannot be expressed as a sum of two primes$$). I'm not quite interested in such examples.










share|cite|improve this question











$endgroup$
















    11












    $begingroup$


    I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




    Is there a recent survey on the subject or an open problem section from a recent conference ?



    Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




    The examples I found are:



    • the well known language of Primitive words $Q = > 1) $ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

    • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)

    Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_Goldbach = 1^2n mid 2n$ cannot be expressed as a sum of two primes$$). I'm not quite interested in such examples.










    share|cite|improve this question











    $endgroup$














      11












      11








      11


      4



      $begingroup$


      I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




      Is there a recent survey on the subject or an open problem section from a recent conference ?



      Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




      The examples I found are:



      • the well known language of Primitive words $Q = > 1) $ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

      • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)

      Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_Goldbach = 1^2n mid 2n$ cannot be expressed as a sum of two primes$$). I'm not quite interested in such examples.










      share|cite|improve this question











      $endgroup$




      I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




      Is there a recent survey on the subject or an open problem section from a recent conference ?



      Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




      The examples I found are:



      • the well known language of Primitive words $Q = > 1) $ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

      • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)

      Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_Goldbach = 1^2n mid 2n$ cannot be expressed as a sum of two primes$$). I'm not quite interested in such examples.







      reference-request big-list context-free






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 11 hours ago







      Marzio De Biasi

















      asked 14 hours ago









      Marzio De BiasiMarzio De Biasi

      18.5k243113




      18.5k243113




















          2 Answers
          2






          active

          oldest

          votes


















          7












          $begingroup$

          How about the language $L_TP$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_TP$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_TP$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_n+1-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$








          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            11 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
            $endgroup$
            – Aryeh
            11 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            11 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            10 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            10 hours ago



















          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence $bf t = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            6 hours 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: "114"
          ;
          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
          ,
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42658%2flanguages-that-we-cannot-disprove-to-be-context-free%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









          7












          $begingroup$

          How about the language $L_TP$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_TP$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_TP$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_n+1-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$








          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            11 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
            $endgroup$
            – Aryeh
            11 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            11 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            10 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            10 hours ago
















          7












          $begingroup$

          How about the language $L_TP$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_TP$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_TP$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_n+1-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$








          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            11 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
            $endgroup$
            – Aryeh
            11 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            11 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            10 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            10 hours ago














          7












          7








          7





          $begingroup$

          How about the language $L_TP$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_TP$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_TP$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_n+1-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$



          How about the language $L_TP$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_TP$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_TP$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_n+1-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 10 hours ago

























          answered 13 hours ago









          AryehAryeh

          5,84411840




          5,84411840







          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            11 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
            $endgroup$
            – Aryeh
            11 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            11 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            10 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            10 hours ago













          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            11 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
            $endgroup$
            – Aryeh
            11 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            11 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            10 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            10 hours ago








          2




          2




          $begingroup$
          Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
          $endgroup$
          – Marzio De Biasi
          11 hours ago




          $begingroup$
          Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
          $endgroup$
          – Marzio De Biasi
          11 hours ago












          $begingroup$
          If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
          $endgroup$
          – Aryeh
          11 hours ago




          $begingroup$
          If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
          $endgroup$
          – Aryeh
          11 hours ago












          $begingroup$
          I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
          $endgroup$
          – Marzio De Biasi
          11 hours ago




          $begingroup$
          I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
          $endgroup$
          – Marzio De Biasi
          11 hours ago




          1




          1




          $begingroup$
          If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
          $endgroup$
          – Emil Jeřábek
          10 hours ago




          $begingroup$
          If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
          $endgroup$
          – Emil Jeřábek
          10 hours ago




          1




          1




          $begingroup$
          Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
          $endgroup$
          – Emil Jeřábek
          10 hours ago





          $begingroup$
          Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
          $endgroup$
          – Emil Jeřábek
          10 hours ago












          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence $bf t = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            6 hours ago















          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence $bf t = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            6 hours ago













          6












          6








          6





          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence $bf t = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$



          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence $bf t = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 8 hours ago









          Jeffrey ShallitJeffrey Shallit

          6,4832635




          6,4832635











          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            6 hours ago
















          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            6 hours ago















          $begingroup$
          Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
          $endgroup$
          – Marzio De Biasi
          6 hours ago




          $begingroup$
          Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
          $endgroup$
          – Marzio De Biasi
          6 hours ago

















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Theoretical 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%2fcstheory.stackexchange.com%2fquestions%2f42658%2flanguages-that-we-cannot-disprove-to-be-context-free%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

          Францішак Багушэвіч Змест Сям'я | Біяграфія | Творчасць | Мова Багушэвіча | Ацэнкі дзейнасці | Цікавыя факты | Спадчына | Выбраная бібліяграфія | Ушанаванне памяці | У філатэліі | Зноскі | Літаратура | Спасылкі | НавігацыяЛяхоўскі У. Рупіўся дзеля Бога і людзей: Жыццёвы шлях Лявона Вітан-Дубейкаўскага // Вольскі і Памідораў з песняй пра немца Адвакат, паэт, народны заступнік Ашмянскі веснікВ Минске появится площадь Богушевича и улица Сырокомли, Белорусская деловая газета, 19 июля 2001 г.Айцец беларускай нацыянальнай ідэі паўстаў у бронзе Сяргей Аляксандравіч Адашкевіч (1918, Мінск). 80-я гады. Бюст «Францішак Багушэвіч».Яўген Мікалаевіч Ціхановіч. «Партрэт Францішка Багушэвіча»Мікола Мікалаевіч Купава. «Партрэт зачынальніка новай беларускай літаратуры Францішка Багушэвіча»Уладзімір Іванавіч Мелехаў. На помніку «Змагарам за родную мову» Барэльеф «Францішак Багушэвіч»Памяць пра Багушэвіча на Віленшчыне Страчаная сталіца. Беларускія шыльды на вуліцах Вільні«Krynica». Ideologia i przywódcy białoruskiego katolicyzmuФранцішак БагушэвічТворы на knihi.comТворы Францішка Багушэвіча на bellib.byСодаль Уладзімір. Францішак Багушэвіч на Лідчыне;Луцкевіч Антон. Жыцьцё і творчасьць Фр. Багушэвіча ў успамінах ягоных сучасьнікаў // Запісы Беларускага Навуковага таварыства. Вільня, 1938. Сшытак 1. С. 16-34.Большая российская1188761710000 0000 5537 633Xn9209310021619551927869394п

          Беларусь Змест Назва Гісторыя Геаграфія Сімволіка Дзяржаўны лад Палітычныя партыі Міжнароднае становішча і знешняя палітыка Адміністрацыйны падзел Насельніцтва Эканоміка Культура і грамадства Сацыяльная сфера Узброеныя сілы Заўвагі Літаратура Спасылкі НавігацыяHGЯOiТоп-2011 г. (па версіі ej.by)Топ-2013 г. (па версіі ej.by)Топ-2016 г. (па версіі ej.by)Топ-2017 г. (па версіі ej.by)Нацыянальны статыстычны камітэт Рэспублікі БеларусьШчыльнасць насельніцтва па краінахhttp://naviny.by/rubrics/society/2011/09/16/ic_articles_116_175144/А. Калечыц, У. Ксяндзоў. Спробы засялення краю неандэртальскім чалавекам.І ў Менску былі мамантыА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіГ. Штыхаў. Балты і славяне ў VI—VIII стст.М. Клімаў. Полацкае княства ў IX—XI стст.Г. Штыхаў, В. Ляўко. Палітычная гісторыя Полацкай зямліГ. Штыхаў. Дзяржаўны лад у землях-княствахГ. Штыхаў. Дзяржаўны лад у землях-княствахБеларускія землі ў складзе Вялікага Княства ЛітоўскагаЛюблінская унія 1569 г."The Early Stages of Independence"Zapomniane prawdy25 гадоў таму было аб'яўлена, што Язэп Пілсудскі — беларус (фота)Наша вадаДакументы ЧАЭС: Забруджванне тэрыторыі Беларусі « ЧАЭС Зона адчужэнняСведения о политических партиях, зарегистрированных в Республике Беларусь // Министерство юстиции Республики БеларусьСтатыстычны бюлетэнь „Полаўзроставая структура насельніцтва Рэспублікі Беларусь на 1 студзеня 2012 года і сярэднегадовая колькасць насельніцтва за 2011 год“Индекс человеческого развития Беларуси — не было бы нижеБеларусь занимает первое место в СНГ по индексу развития с учетом гендерного факцёраНацыянальны статыстычны камітэт Рэспублікі БеларусьКанстытуцыя РБ. Артыкул 17Трансфармацыйныя задачы БеларусіВыйсце з крызісу — далейшае рэфармаванне Беларускі рубель — сусветны лідар па дэвальвацыяхПра змену коштаў у кастрычніку 2011 г.Бядней за беларусаў у СНД толькі таджыкіСярэдні заробак у верасні дасягнуў 2,26 мільёна рублёўЭканомікаГаласуем за ТОП-100 беларускай прозыСучасныя беларускія мастакіАрхитектура Беларуси BELARUS.BYА. Каханоўскі. Культура Беларусі ўсярэдзіне XVII—XVIII ст.Анталогія беларускай народнай песні, гуказапісы спеваўБеларускія Музычныя IнструментыБеларускі рок, які мы страцілі. Топ-10 гуртоў«Мясцовы час» — нязгаслая легенда беларускай рок-музыкіСЯРГЕЙ БУДКІН. МЫ НЯ ЗНАЕМ СВАЁЙ МУЗЫКІМ. А. Каладзінскі. НАРОДНЫ ТЭАТРМагнацкія культурныя цэнтрыПублічная дыскусія «Беларуская новая пьеса: без беларускай мовы ці беларуская?»Беларускія драматургі па-ранейшаму лепш ставяцца за мяжой, чым на радзіме«Працэс незалежнага кіно пайшоў, і дзяржаву турбуе яго непадкантрольнасць»Беларускія філосафы ў пошуках прасторыВсе идём в библиотекуАрхіваванаАб Нацыянальнай праграме даследавання і выкарыстання касмічнай прасторы ў мірных мэтах на 2008—2012 гадыУ космас — разам.У суседнім з Барысаўскім раёне пабудуюць Камандна-вымяральны пунктСвяты і абрады беларусаў«Мірныя бульбашы з малой краіны» — 5 непраўдзівых стэрэатыпаў пра БеларусьМ. Раманюк. Беларускае народнае адзеннеУ Беларусі скарачаецца колькасць злачынстваўЛукашэнка незадаволены мінскімі ўладамі Крадзяжы складаюць у Мінску каля 70% злачынстваў Узровень злачыннасці ў Мінскай вобласці — адзін з самых высокіх у краіне Генпракуратура аналізуе стан са злачыннасцю ў Беларусі па каэфіцыенце злачыннасці У Беларусі стабілізавалася крымінагеннае становішча, лічыць генпракурорЗамежнікі сталі здзяйсняць у Беларусі больш злачынстваўМУС Беларусі турбуе рост рэцыдыўнай злачыннасціЯ з ЖЭСа. Дазволіце вас абкрасці! Рэйтынг усіх службаў і падраздзяленняў ГУУС Мінгарвыканкама вырасАб КДБ РБГісторыя Аператыўна-аналітычнага цэнтра РБГісторыя ДКФРТаможняagentura.ruБеларусьBelarus.by — Афіцыйны сайт Рэспублікі БеларусьСайт урада БеларусіRadzima.org — Збор архітэктурных помнікаў, гісторыя Беларусі«Глобус Беларуси»Гербы и флаги БеларусиАсаблівасці каменнага веку на БеларусіА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіУ. Ксяндзоў. Сярэдні каменны век (мезаліт). Засяленне краю плямёнамі паляўнічых, рыбакоў і збіральнікаўА. Калечыц, М. Чарняўскі. Плямёны на тэрыторыі Беларусі ў новым каменным веку (неаліце)А. Калечыц, У. Ксяндзоў, М. Чарняўскі. Гаспадарчыя заняткі ў каменным векуЭ. Зайкоўскі. Духоўная культура ў каменным векуАсаблівасці бронзавага веку на БеларусіФарміраванне супольнасцей ранняга перыяду бронзавага векуФотографии БеларусиРоля беларускіх зямель ва ўтварэнні і ўмацаванні ВКЛВ. Фадзеева. З гісторыі развіцця беларускай народнай вышыўкіDMOZGran catalanaБольшая российскаяBritannica (анлайн)Швейцарскі гістарычны15325917611952699xDA123282154079143-90000 0001 2171 2080n9112870100577502ge128882171858027501086026362074122714179пппппп

          ValueError: Expected n_neighbors <= n_samples, but n_samples = 1, n_neighbors = 6 (SMOTE) The 2019 Stack Overflow Developer Survey Results Are InCan SMOTE be applied over sequence of words (sentences)?ValueError when doing validation with random forestsSMOTE and multi class oversamplingLogic behind SMOTE-NC?ValueError: Error when checking target: expected dense_1 to have shape (7,) but got array with shape (1,)SmoteBoost: Should SMOTE be ran individually for each iteration/tree in the boosting?solving multi-class imbalance classification using smote and OSSUsing SMOTE for Synthetic Data generation to improve performance on unbalanced dataproblem of entry format for a simple model in KerasSVM SMOTE fit_resample() function runs forever with no result