Otdfbt

Do warforged have souls?

What is the role of 'For' here?

How do I design a circuit to convert a 100 mV and 50 Hz sine wave to a square wave?

Student Loan from years ago pops up and is taking my salary

Accepted by European university, rejected by all American ones I applied to? Possible reasons?

Button changing its text & action. Good or terrible?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

Sort list of array linked objects by keys and values

Do working physicists consider Newtonian mechanics to be "falsified"?

Did the new image of black hole confirm the general theory of relativity?

How to read αἱμύλιος or when to aspirate

What information about me do stores get via my credit card?

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

How do you keep chess fun when your opponent constantly beats you?

Word to describe a time interval

One-dimensional Japanese puzzle

Is this wall load bearing? Blueprints and photos attached

What can I do if neighbor is blocking my solar panels intentionally?

Working through the single responsibility principle (SRP) in Python when calls are expensive

What aspect of planet Earth must be changed to prevent the industrial revolution?

Can each chord in a progression create its own key?

different output for groups and groups USERNAME after adding a username to a group

Why are PDP-7-style microprogrammed instructions out of vogue?

Single author papers against my advisor's will?

Language whose intersection with a CFL is always a CFL

1

$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

share|cite|improve this question

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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 | 

1

$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

share|cite|improve this question

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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

share|cite|improve this question

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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$

share|cite|improve this question

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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.

share|cite|improve this question

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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 Apr 8 at 12:34

Yuval Filmus

196k15185349

edited Apr 8 at 12:34

Yuval Filmus

196k15185349

asked Apr 8 at 12:29

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 Apr 8 at 12:29

Matan HalfonMatan Halfon

91

1 Answer
1

active

oldest

votes

2

$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.

share|cite|improve this answer

edited Apr 9 at 5:03

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

$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
  Apr 8 at 17:26
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 17:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you don't know something, why not look it up? Be curious.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 21:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:17
  

  
  
  
  

 | 
show 2 more comments

Your Answer

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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

2

$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.

share|cite|improve this answer

edited Apr 9 at 5:03

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

$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
  Apr 8 at 17:26
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 17:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you don't know something, why not look it up? Be curious.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 21:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:17
  

  
  
  
  

 | 
show 2 more comments

2

$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.

share|cite|improve this answer

edited Apr 9 at 5:03

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

$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
  Apr 8 at 17:26
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Unfortunately I don’t care about this sort of artificial constraint. In mathematics we can use everything we know.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 17:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you don't know something, why not look it up? Be curious.
  $endgroup$
  – Yuval Filmus
  Apr 8 at 21:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 9 at 12:17
  

  
  
  
  

 | 
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.

share|cite|improve this answer

edited Apr 9 at 5:03

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

$endgroup$

share|cite|improve this answer

edited Apr 9 at 5:03

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349

answered Apr 8 at 12:44

Yuval FilmusYuval Filmus

196k15185349