Language involving irrational number is not a CFLHow to prove that a language is not regular?Why is $L= 0^n 1^n $ 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?
Theorists sure want true answers to this!
Fair gambler's ruin problem intuition
Why is the sentence "Das ist eine Nase" correct?
How do conventional missiles fly?
My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?
Do creatures with a listed speed of "0 ft., fly 30 ft. (hover)" ever touch the ground?
How to stretch the corners of this image so that it looks like a perfect rectangle?
Bullying boss launched a smear campaign and made me unemployable
Can a virus destroy the BIOS of a modern computer?
Was the old ablative pronoun "med" or "mēd"?
What exactly is ineptocracy?
In Bayesian inference, why are some terms dropped from the posterior predictive?
Solving an equation with constraints
What Exploit Are These User Agents Trying to Use?
Knowledge-based authentication using Domain-driven Design in C#
Is there a hemisphere-neutral way of specifying a season?
GFCI outlets - can they be repaired? Are they really needed at the end of a circuit?
Implication of namely
How do I exit BASH while loop using modulus operator?
How to remove border from elements in the last row?
What do you call someone who asks many questions?
Ambiguity in the definition of entropy
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
Is it a bad idea to plug the other end of ESD strap to wall ground?
Language involving irrational number is not a CFL
How to prove that a language is not regular?Why is $L= 0^n 1^n $ 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?
$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!
formal-languages automata context-free
$endgroup$
add a comment |
$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!
formal-languages automata context-free
$endgroup$
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
4
$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
Mar 20 at 19:36
$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$
– user101859
Mar 20 at 22:42
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14
add a comment |
$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!
formal-languages automata context-free
$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
formal-languages automata context-free
edited Mar 20 at 23:12
D.W.♦
103k12129293
103k12129293
asked Mar 20 at 15:25
user101859
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
4
$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
Mar 20 at 19:36
$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$
– user101859
Mar 20 at 22:42
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14
add a comment |
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
4
$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
Mar 20 at 19:36
$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$
– user101859
Mar 20 at 22:42
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
4
4
$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
Mar 20 at 19:36
$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
Mar 20 at 19:36
$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$
– user101859
Mar 20 at 22:42
$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$
– user101859
Mar 20 at 22:42
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14
add a comment |
2 Answers
2
active
oldest
votes
$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)$.
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
add a comment |
$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.
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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)$.
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
add a comment |
$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)$.
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
add a comment |
$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)$.
$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)$.
answered Mar 20 at 18:02
Yuval FilmusYuval Filmus
195k15184349
195k15184349
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
add a comment |
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
$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$
– user101859
Mar 20 at 18:57
$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$
– user101859
Mar 20 at 18:57
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
$begingroup$
No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < gamma$.
$endgroup$
– Yuval Filmus
Mar 20 at 19:09
add a comment |
$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.
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
add a comment |
$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.
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
add a comment |
$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.
$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.
edited Mar 20 at 20:20
answered Mar 20 at 19:27
Apass.JackApass.Jack
13.8k1940
13.8k1940
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
add a comment |
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
$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
Mar 20 at 19:45
$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
Mar 20 at 19:45
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$begingroup$
The usual construction is to take convergents of the continued fraction.
$endgroup$
– Yuval Filmus
Mar 20 at 20:03
$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
Mar 20 at 20:21
$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
Mar 20 at 20:21
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$begingroup$
Have you tried applying Parikh’s theorem?
$endgroup$
– Yuval Filmus
Mar 20 at 15:44
$begingroup$
Why not show that it’s not semilinear directly? Use the definition.
$endgroup$
– Yuval Filmus
Mar 20 at 15:53
4
$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
Mar 20 at 19:36
$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$
– user101859
Mar 20 at 22:42
$begingroup$
I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem!
$endgroup$
– D.W.♦
Mar 20 at 23:14