Language whose intersection with a CFL is always a CFL The 2019 Stack Overflow Developer Survey Results Are InIf $L_1$ is regular and $L_1 cap L_2$ context-free, is $L_2$ always context-free?Can every context free language written as a intersection of another context free language and a regular language?Intersection of a language with a regular language imply context freeProving/Disproving that language L is non-regular/CFLLower bound for number of nonterminals in a CFGIs intersection of regular language and context free language is “always” context free languageProof Idea: How to prove the intersection of regular language and CFL is a CFL?CFL Intersection with Regular Language proveGiven a CFL L and a regular language R, is $overlineL cap R = emptyset$ decidable or undecidable?Is a kind of reverse Kleene star of a context-free language context-free?
What do the Banks children have against barley water?
Why isn't airport relocation done gradually?
Is it possible for the two major parties in the UK to form a coalition with each other instead of a much smaller party?
How come people say “Would of”?
Could JWST stay at L2 "forever"?
How long do I have to send payment?
Why can Shazam do this?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
It's possible to achieve negative score?
Dual Citizen. Exited the US on Italian passport recently
Does a dangling wire really electrocute me if I'm standing in water?
Access elements in std::string where positon of string is greater than its size
How to change the limits of integration
Patience, young "Padovan"
How to create dashed lines/arrows in Illustrator
On the insanity of kings as an argument against monarchy
What does "sndry explns" mean in one of the Hitchhiker's guide books?
Can distinct morphisms between curves induce the same morphism on singular cohomology?
"To split hairs" vs "To be pedantic"
The difference between dialogue marks
I looked up a future colleague on LinkedIn before I started a job. I told my colleague about it and he seemed surprised. Should I apologize?
What is the steepest angle that a canal can be traversable without locks?
Inline version of a function returns different value than non-inline version
Is flight data recorder erased after every flight?
Language whose intersection with a CFL is always a CFL
The 2019 Stack Overflow Developer Survey Results Are InIf $L_1$ is regular and $L_1 cap L_2$ context-free, is $L_2$ always context-free?Can every context free language written as a intersection of another context free language and a regular language?Intersection of a language with a regular language imply context freeProving/Disproving that language L is non-regular/CFLLower bound for number of nonterminals in a CFGIs intersection of regular language and context free language is “always” context free languageProof Idea: How to prove the intersection of regular language and CFL is a CFL?CFL Intersection with Regular Language proveGiven a CFL L and a regular language R, is $overlineL cap R = emptyset$ decidable or undecidable?Is a kind of reverse Kleene star of a context-free language context-free?
$begingroup$
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm pretty sure there is no counterexample.
formal-languages regular-languages context-free
edited yesterday
Yuval Filmus
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm pretty sure there is no counterexample.
formal-languages regular-languages context-free
edited yesterday
Yuval Filmus
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm pretty sure there is no counterexample.
formal-languages regular-languages context-free
edited yesterday
Yuval Filmus
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm pretty sure there is no counterexample.
formal-languages regular-languages context-free
formal-languages regular-languages context-free
edited yesterday
Yuval Filmus
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Yuval Filmus
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Yuval Filmus
196k15184349
edited yesterday
Yuval Filmus
196k15184349
edited yesterday
Yuval Filmus
196k15184349
196k15184349
asked yesterday
Matan HalfonMatan Halfon
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Matan HalfonMatan Halfon
91
asked yesterday
Matan HalfonMatan Halfon
91
91
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Matan Halfon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $L = a^n b^n : n geq 0$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 cap a^* b^*$, and note that $L_1$ is context-free and $L cap L_0 = L cap L_1$. Let $S = (i,j) : a^i b^j in L_1$.
According to Parikh's theorem, the set $S$ is semilinear. The set $D = (n,n) geq 0$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S cap D$ is also semilinear. Since $S cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m geq 1$ and a subset $A subseteq 0,ldots,m-1$ such that
$$
L cap L_1 = F Delta a^n b^n : n bmod m in A ,
$$
where $Delta$ is symmetric difference. It is easy to check that $a^nb^n : n bmod m in A$ is context-free, and so $L cap L_1$ is context-free.
Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
|
show 2 more comments
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
);
);
Matan Halfon is a new contributor. Be nice, and check out our Code of Conduct.
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%2f106657%2flanguage-whose-intersection-with-a-cfl-is-always-a-cfl%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $L = a^n b^n : n geq 0$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 cap a^* b^*$, and note that $L_1$ is context-free and $L cap L_0 = L cap L_1$. Let $S = (i,j) : a^i b^j in L_1$.
According to Parikh's theorem, the set $S$ is semilinear. The set $D = (n,n) geq 0$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S cap D$ is also semilinear. Since $S cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m geq 1$ and a subset $A subseteq 0,ldots,m-1$ such that
$$
L cap L_1 = F Delta a^n b^n : n bmod m in A ,
$$
where $Delta$ is symmetric difference. It is easy to check that $a^nb^n : n bmod m in A$ is context-free, and so $L cap L_1$ is context-free.
Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
|
show 2 more comments
$begingroup$
Let $L = a^n b^n : n geq 0$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 cap a^* b^*$, and note that $L_1$ is context-free and $L cap L_0 = L cap L_1$. Let $S = (i,j) : a^i b^j in L_1$.
According to Parikh's theorem, the set $S$ is semilinear. The set $D = (n,n) geq 0$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S cap D$ is also semilinear. Since $S cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m geq 1$ and a subset $A subseteq 0,ldots,m-1$ such that
$$
L cap L_1 = F Delta a^n b^n : n bmod m in A ,
$$
where $Delta$ is symmetric difference. It is easy to check that $a^nb^n : n bmod m in A$ is context-free, and so $L cap L_1$ is context-free.
Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
|
show 2 more comments
$begingroup$
Let $L = a^n b^n : n geq 0$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 cap a^* b^*$, and note that $L_1$ is context-free and $L cap L_0 = L cap L_1$. Let $S = (i,j) : a^i b^j in L_1$.
According to Parikh's theorem, the set $S$ is semilinear. The set $D = (n,n) geq 0$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S cap D$ is also semilinear. Since $S cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m geq 1$ and a subset $A subseteq 0,ldots,m-1$ such that
$$
L cap L_1 = F Delta a^n b^n : n bmod m in A ,
$$
where $Delta$ is symmetric difference. It is easy to check that $a^nb^n : n bmod m in A$ is context-free, and so $L cap L_1$ is context-free.
Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
Let $L = a^n b^n : n geq 0$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 cap a^* b^*$, and note that $L_1$ is context-free and $L cap L_0 = L cap L_1$. Let $S = (i,j) : a^i b^j in L_1$.
According to Parikh's theorem, the set $S$ is semilinear. The set $D = (n,n) geq 0$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S cap D$ is also semilinear. Since $S cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m geq 1$ and a subset $A subseteq 0,ldots,m-1$ such that
$$
L cap L_1 = F Delta a^n b^n : n bmod m in A ,
$$
where $Delta$ is symmetric difference. It is easy to check that $a^nb^n : n bmod m in A$ is context-free, and so $L cap L_1$ is context-free.
Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
edited 22 hours ago
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
answered yesterday
Yuval FilmusYuval Filmus
196k15184349
196k15184349
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
|
show 2 more comments
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
i dont know (or allowed )to use the Parikj's theorem there is any way you can show it without the linearity, thanks a lot
$endgroup$
– Matan Halfon
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
I wrote this once before but it must've vanished in the ether: your $L$ is context-free. So what am I missing here?
$endgroup$
– Kai
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
$begingroup$
@Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim.
$endgroup$
– Peter Leupold
14 hours ago
|
show 2 more comments
Matan Halfon is a new contributor. Be nice, and check out our Code of Conduct.
Matan Halfon is a new contributor. Be nice, and check out our Code of Conduct.
Matan Halfon is a new contributor. Be nice, and check out our Code of Conduct.
Matan Halfon 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.
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%2f106657%2flanguage-whose-intersection-with-a-cfl-is-always-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
