- Thread starter
- #1

- Apr 13, 2013

- 3,723

Let S be a context-free language and L a regular language.Is there a case that the language S-L is not context-free?

How can I check this?

- Thread starter evinda
- Start date

- Thread starter
- #1

- Apr 13, 2013

- 3,723

Let S be a context-free language and L a regular language.Is there a case that the language S-L is not context-free?

How can I check this?

- Thread starter
- #2

- Apr 13, 2013

- 3,723

I think that it is not possible that the language S-L is not context-free,because of the closure properties.Am I right?

Let S be a context-free language and L a regular language.Is there a case that the language S-L is not context-free?

How can I check this?

- Jan 30, 2012

- 2,502

Yes, the class of context-free languages is closed under intersection with regular languages..I think that it is not possible that the language S-L is not context-free,because of the closure properties.Am I right?

- Thread starter
- #4

- Apr 13, 2013

- 3,723

Nice... and how can I prove this?Could you give me an example?Yes, the class of context-free languages is closed under intersection with regular languages..

- Jan 30, 2012

- 2,502

It is a good exercise to think why this construction does not work for combining two pushdown automata (which are inherently nondeterministic) and thus proving that CFL are closed under intersection (which is not the case).

- Thread starter
- #6

- Apr 13, 2013

- 3,723

To use the closure property of intersection,do I have to use the fact that [tex]S-L=S\cap L^{c}[/tex] ,where [tex] L^{c} [/tex] is the complement of L and is also regular?

It is a good exercise to think why this construction does not work for combining two pushdown automata (which are inherently nondeterministic) and thus proving that CFL are closed under intersection (which is not the case).

- Jan 30, 2012

- 2,502

That's right.To use the closure property of intersection,do I have to use the fact that [tex]S-L=S\cap L^{c}[/tex] ,where [tex] L^{c} [/tex] is the complement of L and is also regular?

- Thread starter
- #8

- Apr 13, 2013

- 3,723

Nice,thank you!! And what's about the language L-S?Is it also context-free and do I have to show it with the same way?That's right.

- Jan 30, 2012

- 2,502

Context-free languages are not closed under complementation (nor intersection). And since the language of all words is regular, the difference of regular and CF is not CF in general.And what's about the language L-S?Is it also context-free and do I have to show it with the same way?

- Thread starter
- #10

- Apr 13, 2013

- 3,723

Nice,thank you very much!!! And...merry Christmas!!!Context-free languages are not closed under complementation (nor intersection). And since the language of all words is regular, the difference of regular and CF is not CF in general.

- Jan 30, 2012

- 2,502

Merci! And same to you!And...merry Christmas!!!

- Thread starter
- #12

- Apr 13, 2013

- 3,723

To show that S-L is context-free,could I also show that each regular language is context-free and that the set of all regular languages is a subset of the set of the context-free languages?So,the difference is only the set of the context-free languages.Or am I wrong?

It is a good exercise to think why this construction does not work for combining two pushdown automata (which are inherently nondeterministic) and thus proving that CFL are closed under intersection (which is not the case).

- Jan 30, 2012

- 2,502

- Thread starter
- #14

- Apr 13, 2013

- 3,723

From the image:logicof this argument in greater detail. That is, suppose that we know that regular languages are context-free. How do we use this fact to prove that S - L is context-free?

we see that the set of the regular languages is a proper subset of the set of the context-free languages.So,if we subtract the regular language from the context-free one,the set that remains is context-free.Can I say it like that?

- Jan 30, 2012

- 2,502

This is true.the set of the regular languages is a proper subset of the set of the context-free languages.

And this is a completely different thing. The first quote talks about the difference between theSo,if we subtract the regular language from the context-free one,the set that remains is context-free.

- Thread starter
- #16

- Apr 13, 2013

- 3,723

I understand...Thanks a lot!!!This is true.

And this is a completely different thing. The first quote talks about the difference between thesetof context-free languages and thesetof regular languages, and the second quote talks about the difference between anindividualcontext-free language and anindividualregular language.