Language involving irrational number is not a CFLHow to prove that a language is not regular?Why is $L= n geq 1 $ not regular language?Prove that the language of unary not-prime numbers satisfies the Pumping LemmaAlgorithm to test whether a language is context-freeUsing the Pumping Lemma to show that the language $a^n b a^n$ is not regularA non-regular language satisfying the pumping lemmaProving non-regularity of $u u^R v$?Prove using pumping free lemma for context-free languagesProve that $L_1 = , 0^m 1^k 2^n ,vert, lvert m - n rvert = k ,$ is not regular using Pumping lemmaPumping lemma for context-free languages - Am I doing it right?

Do you waste sorcery points if you try to apply metamagic to a spell from a scroll but fail to cast it?

Anime with legendary swords made from talismans and a man who could change them with a shattered body

Proving an identity involving cross products and coplanar vectors

Why does the Persian emissary display a string of crowned skulls?

Can I say "fingers" when referring to toes?

Giving feedback to someone without sounding prejudiced

How to write Quadratic equation with negative coefficient

Is there a distance limit for minecart tracks?

Why is participating in the European Parliamentary elections used as a threat?

Why the "ls" command is showing the permissions of files in a FAT32 partition?

"Oh no!" in Latin

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

Identifying "long and narrow" polygons in with PostGIS

Sigmoid with a slope but no asymptotes?

What does "tick" mean in this sentence?

Why would five hundred and five be same as one?

Possible Eco thriller, man invents a device to remove rain from glass

If A is dense in Q, then it must be dense in R.

Quoting Keynes in a lecture

Animation: customize bounce interpolation

What in this world is she trying to say?

How would a solely written language work mechanically

Showing mass murder in a kid's book

Unable to disable Microsoft Store in domain environment



Language involving irrational number is not a CFL


How to prove that a language is not regular?Why is $L= n geq 1 $ not regular language?Prove that the language of unary not-prime numbers satisfies the Pumping LemmaAlgorithm to test whether a language is context-freeUsing the Pumping Lemma to show that the language $a^n b a^n$ is not regularA non-regular language satisfying the pumping lemmaProving non-regularity of $u u^R v$?Prove using pumping free lemma for context-free languagesProve that $L_1 = , 0^m 1^k 2^n ,vert, lvert m - n rvert = k ,$ is not regular using Pumping lemmaPumping lemma for context-free languages - Am I doing it right?













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
    47 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
    47 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 16 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 8 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
    47 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
    47 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
47 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
47 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
    3 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
    3 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
    3 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 4 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
    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$
    @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
    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 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
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
3 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

How should I use the fbox command correctly to avoid producing a Bad Box message?How to put a long piece of text in a box?How to specify height and width of fboxIs there an arrayrulecolor-like command to change the rule color of fbox?What is the command to highlight bad boxes in pdf?Why does fbox sometimes place the box *over* the graphic image?how to put the text in the boxHow to create command for a box where text inside the box can automatically adjust?how can I make an fbox like command with certain color, shape and width of border?how to use fbox in align modeFbox increase the spacing between the box and it content (inner margin)how to change the box height of an equationWhat is the use of the hbox in a newcommand command?

Doxepinum Nexus interni Notae | Tabula navigationis3158DB01142WHOa682390"Structural Analysis of the Histamine H1 Receptor""Transdermal and Topical Drug Administration in the Treatment of Pain""Antidepressants as antipruritic agents: A review"

inputenc: Unicode character … not set up for use with LaTeX The Next CEO of Stack OverflowEntering Unicode characters in LaTeXHow to solve the `Package inputenc Error: Unicode char not set up for use with LaTeX` problem?solve “Unicode char is not set up for use with LaTeX” without special handling of every new interesting UTF-8 characterPackage inputenc Error: Unicode character ² (U+B2)(inputenc) not set up for use with LaTeX. acroI2C[I²C]package inputenc error unicode char (u + 190) not set up for use with latexPackage inputenc Error: Unicode char u8:′ not set up for use with LaTeX. 3′inputenc Error: Unicode char u8: not set up for use with LaTeX with G-BriefPackage Inputenc Error: Unicode char u8: not set up for use with LaTeXPackage inputenc Error: Unicode char ́ (U+301)(inputenc) not set up for use with LaTeX. includePackage inputenc Error: Unicode char ̂ (U+302)(inputenc) not set up for use with LaTeX. … $widehatleft (OA,AA' right )$Package inputenc Error: Unicode char â„¡ (U+2121)(inputenc) not set up for use with LaTeX. printbibliography[heading=bibintoc]Package inputenc Error: Unicode char − (U+2212)(inputenc) not set up for use with LaTeXPackage inputenc Error: Unicode character α (U+3B1) not set up for use with LaTeXPackage inputenc Error: Unicode characterError: ! Package inputenc Error: Unicode char ⊘ (U+2298)(inputenc) not set up for use with LaTeX