Language whose intersection with a CFL is always a CFLIf $L_1$ is regular and $L_1 cap L_2$ context-free, is...
Shall I use personal or official e-mail account when registering to external websites for work purpose?
Landlord wants to switch my lease to a "Land contract" to "get back at the city"
Pristine Bit Checking
Can the Produce Flame cantrip be used to grapple, or as an unarmed strike, in the right circumstances?
Map list to bin numbers
Is ipsum/ipsa/ipse a third person pronoun, or can it serve other functions?
Where to refill my bottle in India?
How could a lack of term limits lead to a "dictatorship?"
How to deal with fear of taking dependencies
What do the Banks children have against barley water?
What does 'script /dev/null' do?
Where else does the Shulchan Aruch quote an authority by name?
Landing in very high winds
Calculate Levenshtein distance between two strings in Python
Is it possible to make sharp wind that can cut stuff from afar?
Is it wise to hold on to stock that has plummeted and then stabilized?
Is this food a bread or a loaf?
Copycat chess is back
Doomsday-clock for my fantasy planet
Is there any use for defining additional entity types in a SOQL FROM clause?
Does a dangling wire really electrocute me if I'm standing in water?
aging parents with no investments
Why do UK politicians seemingly ignore opinion polls on Brexit?
When blogging recipes, how can I support both readers who want the narrative/journey and ones who want the printer-friendly recipe?
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 $overline{L} 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 17 hours ago
Yuval Filmus
196k15184349
asked 17 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 17 hours ago
Yuval Filmus
196k15184349
asked 17 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 17 hours ago
Yuval Filmus
196k15184349
asked 17 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 17 hours ago
Yuval Filmus
196k15184349
asked 17 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 17 hours ago
Yuval Filmus
196k15184349
asked 17 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 17 hours ago
Yuval Filmus
196k15184349
edited 17 hours ago
Yuval Filmus
196k15184349
edited 17 hours ago
Yuval Filmus
196k15184349
196k15184349
asked 17 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 17 hours ago
Matan HalfonMatan Halfon
91
asked 17 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 17 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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 17 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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 17 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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 17 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 17 hours ago
Yuval FilmusYuval Filmus
196k15184349
edited 1 hour ago
answered 17 hours ago
Yuval FilmusYuval Filmus
196k15184349
answered 17 hours ago
Yuval FilmusYuval Filmus
196k15184349
answered 17 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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
13 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
13 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
13 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
13 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 hours ago
$begingroup$
If you don't know something, why not look it up? Be curious.
$endgroup$
– Yuval Filmus
8 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
