Language whose intersection with a CFL is always a CFLIf $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?
How can I fix this gap between bookcases I made?
Information to fellow intern about hiring?
A poker game description that does not feel gimmicky
Was there ever an axiom rendered a theorem?
Need help identifying/translating a plaque in Tangier, Morocco
Landing in very high winds
Are cabin dividers used to "hide" the flex of the airplane?
Prime joint compound before latex paint?
Is there any use for defining additional entity types in a SOQL FROM clause?
How do I create uniquely male characters?
Is there a way to make member function NOT callable from constructor?
New order #4: World
What is the command to reset a PC without deleting any files
What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?
Lied on resume at previous job
Ideas for 3rd eye abilities
Unbreakable Formation vs. Cry of the Carnarium
LWC and complex parameters
Denied boarding due to overcrowding, Sparpreis ticket. What are my rights?
Landlord wants to switch my lease to a "Land contract" to "get back at the city"
Copycat chess is back
Is every set a filtered colimit of finite sets?
Why is my log file so massive? 22gb. I am running log backups
Can a planet have a different gravitational pull depending on its location in orbit around its sun?
Language whose intersection with a CFL is always a CFL
If $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 16 hours ago
Yuval Filmus
196k15184349
asked 16 hours ago
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 16 hours ago
Yuval Filmus
196k15184349
asked 16 hours ago
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 16 hours ago
Yuval Filmus
196k15184349
asked 16 hours ago
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 16 hours ago
Yuval Filmus
196k15184349
asked 16 hours ago
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 16 hours ago
Yuval Filmus
196k15184349
asked 16 hours ago
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 16 hours ago
Yuval Filmus
196k15184349
edited 16 hours ago
Yuval Filmus
196k15184349
edited 16 hours ago
Yuval Filmus
196k15184349
196k15184349
asked 16 hours ago
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 16 hours ago
Matan HalfonMatan Halfon
91
asked 16 hours ago
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 16 hours ago
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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
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
);
);
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 16 hours ago
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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
add a comment |
$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 16 hours ago
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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
add a comment |
$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 16 hours ago
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 16 hours ago
Yuval FilmusYuval Filmus
196k15184349
edited 20 mins ago
answered 16 hours ago
Yuval FilmusYuval Filmus
196k15184349
answered 16 hours ago
Yuval FilmusYuval Filmus
196k15184349
answered 16 hours ago
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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
add a comment |
$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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 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
11 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
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
$endgroup$
– Yuval Filmus
11 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
7 hours ago
add a comment |
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
