Language involving irrational number is not a CFLConstructing a Context Free Grammar for checking non-equality of stringsRecursive language with non-recursive subsetsHow can I prove this language is not CFL?How to convert this type of languages to Context Free grammar?Describe the language generated by a given context free grammarProving/Disproving that language L is non-regular/CFLHow is $a^nb^nc^2n$ not a context free language, where as $a^nb^mc^n+m$ is?Proving a grammar/language as not regularWhen proof by induction on length string is not possible?Context-free grammar from language

Can I cause damage to electrical appliances by unplugging them when they are turned on?

Is there a RAID 0 Equivalent for RAM?

What in this world is she trying to say?

What happens if I try to grapple mirror image?

Storage of electrolytic capacitors - how long?

Typing CO_2 easily

How to write Quadratic equation with negative coefficient

Does Doodling or Improvising on the Piano Have Any Benefits?

Limit max CPU usage SQL SERVER with WSRM

Air travel with refrigerated insulin

How to I force windows to use a specific version of SQLCMD?

What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?

Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?

Can you identify this lizard-like creature I observed in the UK?

How to test the sharpness of a knife?

Overlapping circles covering polygon

Is there a distance limit for minecart tracks?

Alignment of six matrices

In One Punch Man, is King actually weak?

Identifying "long and narrow" polygons in with PostGIS

PTIJ: does fasting on Ta'anis Esther give us reward as if we celebrated 2 Purims? (similar to Yom Kippur)

Why is the principal energy of an electron lower for excited electrons in a higher energy state?

How to get directions in deep space?

Animation: customize bounce interpolation



Language involving irrational number is not a CFL


Constructing a Context Free Grammar for checking non-equality of stringsRecursive language with non-recursive subsetsHow can I prove this language is not CFL?How to convert this type of languages to Context Free grammar?Describe the language generated by a given context free grammarProving/Disproving that language L is non-regular/CFLHow is $a^nb^nc^2n$ not a context free language, where as $a^nb^mc^n+m$ is?Proving a grammar/language as not regularWhen proof by induction on length string is not possible?Context-free grammar from language













8












$begingroup$


I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = a^ib^j: i leq j gamma, igeq 0, jgeq 1$ where $gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?



In the case when $gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.



This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.



I would really appreciate any help, or nudges in the right direction. Thank you!










share|cite|improve this question









New contributor




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







$endgroup$











  • $begingroup$
    Have you tried applying Parikh’s theorem?
    $endgroup$
    – Yuval Filmus
    7 hours ago











  • $begingroup$
    Why not show that it’s not semilinear directly? Use the definition.
    $endgroup$
    – Yuval Filmus
    7 hours ago






  • 3




    $begingroup$
    Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
    $endgroup$
    – Hendrik Jan
    3 hours ago











  • $begingroup$
    @ChenyiShiwen, so the pumping lemma does work.
    $endgroup$
    – Apass.Jack
    3 hours ago










  • $begingroup$
    @HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
    $endgroup$
    – ChenyiShiwen
    38 mins ago















8












$begingroup$


I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = a^ib^j: i leq j gamma, igeq 0, jgeq 1$ where $gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?



In the case when $gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.



This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.



I would really appreciate any help, or nudges in the right direction. Thank you!










share|cite|improve this question









New contributor




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







$endgroup$











  • $begingroup$
    Have you tried applying Parikh’s theorem?
    $endgroup$
    – Yuval Filmus
    7 hours ago











  • $begingroup$
    Why not show that it’s not semilinear directly? Use the definition.
    $endgroup$
    – Yuval Filmus
    7 hours ago






  • 3




    $begingroup$
    Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
    $endgroup$
    – Hendrik Jan
    3 hours ago











  • $begingroup$
    @ChenyiShiwen, so the pumping lemma does work.
    $endgroup$
    – Apass.Jack
    3 hours ago










  • $begingroup$
    @HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
    $endgroup$
    – ChenyiShiwen
    38 mins ago













8












8








8





$begingroup$


I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = a^ib^j: i leq j gamma, igeq 0, jgeq 1$ where $gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?



In the case when $gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.



This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.



I would really appreciate any help, or nudges in the right direction. Thank you!










share|cite|improve this question









New contributor




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







$endgroup$




I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = a^ib^j: i leq j gamma, igeq 0, jgeq 1$ where $gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?



In the case when $gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.



This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.



I would really appreciate any help, or nudges in the right direction. Thank you!







formal-languages automata context-free






share|cite|improve this question









New contributor




ChenyiShiwen 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




ChenyiShiwen 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 7 mins ago









D.W.

102k12127291




102k12127291






New contributor




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









asked 7 hours ago









ChenyiShiwenChenyiShiwen

434




434




New contributor




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





New contributor





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






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











  • $begingroup$
    Have you tried applying Parikh’s theorem?
    $endgroup$
    – Yuval Filmus
    7 hours ago











  • $begingroup$
    Why not show that it’s not semilinear directly? Use the definition.
    $endgroup$
    – Yuval Filmus
    7 hours ago






  • 3




    $begingroup$
    Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
    $endgroup$
    – Hendrik Jan
    3 hours ago











  • $begingroup$
    @ChenyiShiwen, so the pumping lemma does work.
    $endgroup$
    – Apass.Jack
    3 hours ago










  • $begingroup$
    @HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
    $endgroup$
    – ChenyiShiwen
    38 mins ago
















  • $begingroup$
    Have you tried applying Parikh’s theorem?
    $endgroup$
    – Yuval Filmus
    7 hours ago











  • $begingroup$
    Why not show that it’s not semilinear directly? Use the definition.
    $endgroup$
    – Yuval Filmus
    7 hours ago






  • 3




    $begingroup$
    Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
    $endgroup$
    – Hendrik Jan
    3 hours ago











  • $begingroup$
    @ChenyiShiwen, so the pumping lemma does work.
    $endgroup$
    – Apass.Jack
    3 hours ago










  • $begingroup$
    @HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
    $endgroup$
    – ChenyiShiwen
    38 mins ago















$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
7 hours ago





$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
7 hours ago













$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
7 hours ago




$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
7 hours ago




3




3




$begingroup$
Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
$endgroup$
– Hendrik Jan
3 hours ago





$begingroup$
Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019.
$endgroup$
– Hendrik Jan
3 hours ago













$begingroup$
@ChenyiShiwen, so the pumping lemma does work.
$endgroup$
– Apass.Jack
3 hours ago




$begingroup$
@ChenyiShiwen, so the pumping lemma does work.
$endgroup$
– Apass.Jack
3 hours ago












$begingroup$
@HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
$endgroup$
– ChenyiShiwen
38 mins ago




$begingroup$
@HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due?
$endgroup$
– ChenyiShiwen
38 mins ago










2 Answers
2






active

oldest

votes


















6












$begingroup$

According to Parikh's theorem, if $L$ were context-free then the set $M = (a,b) : a leq gamma b $ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + mathbbN u_1 + cdots + mathbbN u_ell$, for some $u_i = (a_i,b_i)$.



Obviously $u_0 in M$, and moreover $u_i in M$ for each $i > 0$, since otherwise $u_0 + N u_i notin M$ for large enough $N$. Therefore $g(S) := max(a_0/b_0,ldots,a_ell/b_ell) < gamma$ (since $g(S)$ is rational). This means that every $(a,b) in S$ satisfies $a/b leq g(S)$.



Now suppose that $M$ is the union of $S^(1),ldots,S^(m)$, and define $g = max(g(S^(1)),ldots,g(S^(m))) < gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b leq g < gamma$, and we obtain a contradiction, since $sup a/b : (a,b) in M = gamma$.




When $gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
(a,b) : a leq tfracst b = bigcup_a=0^s-1 (a,lceil tfracts a rceil) + mathbbN (s,t) + mathbbN (0,1).
$$

Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a leq tfracst b$ (since $s = tfracst t$). Conversely, suppose that $a leq fracst b$. While $a geq s$ and $b geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a leq fracstb < s$). Since $a leq fracst b$, necessarily $b geq lceil tfracts a rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,lceil tfracts a rceil)$.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
    $endgroup$
    – ChenyiShiwen
    4 hours ago











  • $begingroup$
    No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
    $endgroup$
    – Yuval Filmus
    4 hours ago


















4












$begingroup$

Every variable except $gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $gamma>0$, there is a sequence of rational numbers $dfraca_1b_1ltdfraca_2b_2ltdfraca_3b_3ltcdots ltgamma$ such that $dfraca_ib_i$ is nearer to $gamma$ than any other rational number smaller than $gamma$ whose denominator is less than $b_i$.




It turns out that the pumping lemma does work!



For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^a_pb^b_p$, a word that is $L$ but "barely". Note that $|s|>b_pge p$. Consider
$s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^nyin L$ for all $nge0$.



Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.



  • If $t_b=0$ or $dfract_at_bgtgamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $gamma$, i.e., $s_nnotin L$.

  • Otherwise, $dfract_at_bltgamma$. Since $t_b<b_p$, $dfract_at_blt dfraca_pb_p$. Hence,
    $dfraca_p-t_ab_p-t_b>dfraca_pb_p$
    Since $b_p-t_b<b_p$, $dfraca_p-t_ab_p-t_b>gamma,$
    which says that $s_0notin L$.

The above contradiction shows that $L$ cannot be context-free.




Here are two related easier exercises.



Exercise 1. Show that $L_gamma=a^lfloor i gammarfloor: iinBbb N$ is not context-free where $gamma$ is an irrational number.



Exercise 2. Show that $L_gamma=a^ib^j: i leq j gamma, i ge0, jge 0$ is context-free where $gamma$ is a rational number.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
    $endgroup$
    – Apass.Jack
    3 hours ago











  • $begingroup$
    The usual construction is to take convergents of the continued fraction.
    $endgroup$
    – Yuval Filmus
    3 hours ago










  • $begingroup$
    @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
    $endgroup$
    – Apass.Jack
    2 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: "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
);



);






ChenyiShiwen 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%2f105836%2flanguage-involving-irrational-number-is-not-a-cfl%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









6












$begingroup$

According to Parikh's theorem, if $L$ were context-free then the set $M = (a,b) : a leq gamma b $ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + mathbbN u_1 + cdots + mathbbN u_ell$, for some $u_i = (a_i,b_i)$.



Obviously $u_0 in M$, and moreover $u_i in M$ for each $i > 0$, since otherwise $u_0 + N u_i notin M$ for large enough $N$. Therefore $g(S) := max(a_0/b_0,ldots,a_ell/b_ell) < gamma$ (since $g(S)$ is rational). This means that every $(a,b) in S$ satisfies $a/b leq g(S)$.



Now suppose that $M$ is the union of $S^(1),ldots,S^(m)$, and define $g = max(g(S^(1)),ldots,g(S^(m))) < gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b leq g < gamma$, and we obtain a contradiction, since $sup a/b : (a,b) in M = gamma$.




When $gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
(a,b) : a leq tfracst b = bigcup_a=0^s-1 (a,lceil tfracts a rceil) + mathbbN (s,t) + mathbbN (0,1).
$$

Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a leq tfracst b$ (since $s = tfracst t$). Conversely, suppose that $a leq fracst b$. While $a geq s$ and $b geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a leq fracstb < s$). Since $a leq fracst b$, necessarily $b geq lceil tfracts a rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,lceil tfracts a rceil)$.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
    $endgroup$
    – ChenyiShiwen
    4 hours ago











  • $begingroup$
    No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
    $endgroup$
    – Yuval Filmus
    4 hours ago















6












$begingroup$

According to Parikh's theorem, if $L$ were context-free then the set $M = (a,b) : a leq gamma b $ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + mathbbN u_1 + cdots + mathbbN u_ell$, for some $u_i = (a_i,b_i)$.



Obviously $u_0 in M$, and moreover $u_i in M$ for each $i > 0$, since otherwise $u_0 + N u_i notin M$ for large enough $N$. Therefore $g(S) := max(a_0/b_0,ldots,a_ell/b_ell) < gamma$ (since $g(S)$ is rational). This means that every $(a,b) in S$ satisfies $a/b leq g(S)$.



Now suppose that $M$ is the union of $S^(1),ldots,S^(m)$, and define $g = max(g(S^(1)),ldots,g(S^(m))) < gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b leq g < gamma$, and we obtain a contradiction, since $sup a/b : (a,b) in M = gamma$.




When $gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
(a,b) : a leq tfracst b = bigcup_a=0^s-1 (a,lceil tfracts a rceil) + mathbbN (s,t) + mathbbN (0,1).
$$

Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a leq tfracst b$ (since $s = tfracst t$). Conversely, suppose that $a leq fracst b$. While $a geq s$ and $b geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a leq fracstb < s$). Since $a leq fracst b$, necessarily $b geq lceil tfracts a rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,lceil tfracts a rceil)$.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
    $endgroup$
    – ChenyiShiwen
    4 hours ago











  • $begingroup$
    No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
    $endgroup$
    – Yuval Filmus
    4 hours ago













6












6








6





$begingroup$

According to Parikh's theorem, if $L$ were context-free then the set $M = (a,b) : a leq gamma b $ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + mathbbN u_1 + cdots + mathbbN u_ell$, for some $u_i = (a_i,b_i)$.



Obviously $u_0 in M$, and moreover $u_i in M$ for each $i > 0$, since otherwise $u_0 + N u_i notin M$ for large enough $N$. Therefore $g(S) := max(a_0/b_0,ldots,a_ell/b_ell) < gamma$ (since $g(S)$ is rational). This means that every $(a,b) in S$ satisfies $a/b leq g(S)$.



Now suppose that $M$ is the union of $S^(1),ldots,S^(m)$, and define $g = max(g(S^(1)),ldots,g(S^(m))) < gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b leq g < gamma$, and we obtain a contradiction, since $sup a/b : (a,b) in M = gamma$.




When $gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
(a,b) : a leq tfracst b = bigcup_a=0^s-1 (a,lceil tfracts a rceil) + mathbbN (s,t) + mathbbN (0,1).
$$

Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a leq tfracst b$ (since $s = tfracst t$). Conversely, suppose that $a leq fracst b$. While $a geq s$ and $b geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a leq fracstb < s$). Since $a leq fracst b$, necessarily $b geq lceil tfracts a rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,lceil tfracts a rceil)$.






share|cite|improve this answer









$endgroup$



According to Parikh's theorem, if $L$ were context-free then the set $M = (a,b) : a leq gamma b $ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + mathbbN u_1 + cdots + mathbbN u_ell$, for some $u_i = (a_i,b_i)$.



Obviously $u_0 in M$, and moreover $u_i in M$ for each $i > 0$, since otherwise $u_0 + N u_i notin M$ for large enough $N$. Therefore $g(S) := max(a_0/b_0,ldots,a_ell/b_ell) < gamma$ (since $g(S)$ is rational). This means that every $(a,b) in S$ satisfies $a/b leq g(S)$.



Now suppose that $M$ is the union of $S^(1),ldots,S^(m)$, and define $g = max(g(S^(1)),ldots,g(S^(m))) < gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b leq g < gamma$, and we obtain a contradiction, since $sup a/b : (a,b) in M = gamma$.




When $gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
(a,b) : a leq tfracst b = bigcup_a=0^s-1 (a,lceil tfracts a rceil) + mathbbN (s,t) + mathbbN (0,1).
$$

Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a leq tfracst b$ (since $s = tfracst t$). Conversely, suppose that $a leq fracst b$. While $a geq s$ and $b geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a leq fracstb < s$). Since $a leq fracst b$, necessarily $b geq lceil tfracts a rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,lceil tfracts a rceil)$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 5 hours ago









Yuval FilmusYuval Filmus

195k14183347




195k14183347











  • $begingroup$
    Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
    $endgroup$
    – ChenyiShiwen
    4 hours ago











  • $begingroup$
    No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
    $endgroup$
    – Yuval Filmus
    4 hours ago
















  • $begingroup$
    Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
    $endgroup$
    – ChenyiShiwen
    4 hours ago











  • $begingroup$
    No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
    $endgroup$
    – Yuval Filmus
    4 hours ago















$begingroup$
Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
$endgroup$
– ChenyiShiwen
4 hours ago





$begingroup$
Nice answer. Just a clarification, the logic behind "every $(a,b) in S$ satisfies $a/b leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)in S$ such that $x/y$ is as large as wanted and therefore larger than $gamma$?
$endgroup$
– ChenyiShiwen
4 hours ago













$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
4 hours ago




$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
4 hours ago











4












$begingroup$

Every variable except $gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $gamma>0$, there is a sequence of rational numbers $dfraca_1b_1ltdfraca_2b_2ltdfraca_3b_3ltcdots ltgamma$ such that $dfraca_ib_i$ is nearer to $gamma$ than any other rational number smaller than $gamma$ whose denominator is less than $b_i$.




It turns out that the pumping lemma does work!



For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^a_pb^b_p$, a word that is $L$ but "barely". Note that $|s|>b_pge p$. Consider
$s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^nyin L$ for all $nge0$.



Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.



  • If $t_b=0$ or $dfract_at_bgtgamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $gamma$, i.e., $s_nnotin L$.

  • Otherwise, $dfract_at_bltgamma$. Since $t_b<b_p$, $dfract_at_blt dfraca_pb_p$. Hence,
    $dfraca_p-t_ab_p-t_b>dfraca_pb_p$
    Since $b_p-t_b<b_p$, $dfraca_p-t_ab_p-t_b>gamma,$
    which says that $s_0notin L$.

The above contradiction shows that $L$ cannot be context-free.




Here are two related easier exercises.



Exercise 1. Show that $L_gamma=a^lfloor i gammarfloor: iinBbb N$ is not context-free where $gamma$ is an irrational number.



Exercise 2. Show that $L_gamma=a^ib^j: i leq j gamma, i ge0, jge 0$ is context-free where $gamma$ is a rational number.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
    $endgroup$
    – Apass.Jack
    3 hours ago











  • $begingroup$
    The usual construction is to take convergents of the continued fraction.
    $endgroup$
    – Yuval Filmus
    3 hours ago










  • $begingroup$
    @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
    $endgroup$
    – Apass.Jack
    2 hours ago
















4












$begingroup$

Every variable except $gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $gamma>0$, there is a sequence of rational numbers $dfraca_1b_1ltdfraca_2b_2ltdfraca_3b_3ltcdots ltgamma$ such that $dfraca_ib_i$ is nearer to $gamma$ than any other rational number smaller than $gamma$ whose denominator is less than $b_i$.




It turns out that the pumping lemma does work!



For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^a_pb^b_p$, a word that is $L$ but "barely". Note that $|s|>b_pge p$. Consider
$s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^nyin L$ for all $nge0$.



Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.



  • If $t_b=0$ or $dfract_at_bgtgamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $gamma$, i.e., $s_nnotin L$.

  • Otherwise, $dfract_at_bltgamma$. Since $t_b<b_p$, $dfract_at_blt dfraca_pb_p$. Hence,
    $dfraca_p-t_ab_p-t_b>dfraca_pb_p$
    Since $b_p-t_b<b_p$, $dfraca_p-t_ab_p-t_b>gamma,$
    which says that $s_0notin L$.

The above contradiction shows that $L$ cannot be context-free.




Here are two related easier exercises.



Exercise 1. Show that $L_gamma=a^lfloor i gammarfloor: iinBbb N$ is not context-free where $gamma$ is an irrational number.



Exercise 2. Show that $L_gamma=a^ib^j: i leq j gamma, i ge0, jge 0$ is context-free where $gamma$ is a rational number.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
    $endgroup$
    – Apass.Jack
    3 hours ago











  • $begingroup$
    The usual construction is to take convergents of the continued fraction.
    $endgroup$
    – Yuval Filmus
    3 hours ago










  • $begingroup$
    @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
    $endgroup$
    – Apass.Jack
    2 hours ago














4












4








4





$begingroup$

Every variable except $gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $gamma>0$, there is a sequence of rational numbers $dfraca_1b_1ltdfraca_2b_2ltdfraca_3b_3ltcdots ltgamma$ such that $dfraca_ib_i$ is nearer to $gamma$ than any other rational number smaller than $gamma$ whose denominator is less than $b_i$.




It turns out that the pumping lemma does work!



For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^a_pb^b_p$, a word that is $L$ but "barely". Note that $|s|>b_pge p$. Consider
$s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^nyin L$ for all $nge0$.



Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.



  • If $t_b=0$ or $dfract_at_bgtgamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $gamma$, i.e., $s_nnotin L$.

  • Otherwise, $dfract_at_bltgamma$. Since $t_b<b_p$, $dfract_at_blt dfraca_pb_p$. Hence,
    $dfraca_p-t_ab_p-t_b>dfraca_pb_p$
    Since $b_p-t_b<b_p$, $dfraca_p-t_ab_p-t_b>gamma,$
    which says that $s_0notin L$.

The above contradiction shows that $L$ cannot be context-free.




Here are two related easier exercises.



Exercise 1. Show that $L_gamma=a^lfloor i gammarfloor: iinBbb N$ is not context-free where $gamma$ is an irrational number.



Exercise 2. Show that $L_gamma=a^ib^j: i leq j gamma, i ge0, jge 0$ is context-free where $gamma$ is a rational number.






share|cite|improve this answer











$endgroup$



Every variable except $gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $gamma>0$, there is a sequence of rational numbers $dfraca_1b_1ltdfraca_2b_2ltdfraca_3b_3ltcdots ltgamma$ such that $dfraca_ib_i$ is nearer to $gamma$ than any other rational number smaller than $gamma$ whose denominator is less than $b_i$.




It turns out that the pumping lemma does work!



For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^a_pb^b_p$, a word that is $L$ but "barely". Note that $|s|>b_pge p$. Consider
$s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^nyin L$ for all $nge0$.



Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.



  • If $t_b=0$ or $dfract_at_bgtgamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $gamma$, i.e., $s_nnotin L$.

  • Otherwise, $dfract_at_bltgamma$. Since $t_b<b_p$, $dfract_at_blt dfraca_pb_p$. Hence,
    $dfraca_p-t_ab_p-t_b>dfraca_pb_p$
    Since $b_p-t_b<b_p$, $dfraca_p-t_ab_p-t_b>gamma,$
    which says that $s_0notin L$.

The above contradiction shows that $L$ cannot be context-free.




Here are two related easier exercises.



Exercise 1. Show that $L_gamma=a^lfloor i gammarfloor: iinBbb N$ is not context-free where $gamma$ is an irrational number.



Exercise 2. Show that $L_gamma=a^ib^j: i leq j gamma, i ge0, jge 0$ is context-free where $gamma$ is a rational number.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 3 hours ago

























answered 3 hours ago









Apass.JackApass.Jack

13.1k1939




13.1k1939











  • $begingroup$
    The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
    $endgroup$
    – Apass.Jack
    3 hours ago











  • $begingroup$
    The usual construction is to take convergents of the continued fraction.
    $endgroup$
    – Yuval Filmus
    3 hours ago










  • $begingroup$
    @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
    $endgroup$
    – Apass.Jack
    2 hours ago

















  • $begingroup$
    The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
    $endgroup$
    – Apass.Jack
    3 hours ago











  • $begingroup$
    The usual construction is to take convergents of the continued fraction.
    $endgroup$
    – Yuval Filmus
    3 hours ago










  • $begingroup$
    @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
    $endgroup$
    – Apass.Jack
    2 hours ago
















$begingroup$
The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
$endgroup$
– Apass.Jack
3 hours ago





$begingroup$
The property in the answer can be proved simply by selecting all rational numbers that is nearer to $gamma$ than all previous numbers in the list of all rational numbers that are smaller than $gamma$ in the order of increasing denominators and, for the same denominators, in increasing order.
$endgroup$
– Apass.Jack
3 hours ago













$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
3 hours ago




$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
3 hours ago












$begingroup$
@YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
$endgroup$
– Apass.Jack
2 hours ago





$begingroup$
@YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".)
$endgroup$
– Apass.Jack
2 hours ago











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









draft saved

draft discarded


















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












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











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














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%2f105836%2flanguage-involving-irrational-number-is-not-a-cfl%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