Welcome to our community

Be a part of something great, join today!

context-free languages!

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hello!! :)
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?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hello!! :)
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?
I think that it is not possible that the language S-L is not context-free,because of the closure properties.Am I right?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
I think that it is not possible that the language S-L is not context-free,because of the closure properties.Am I right?
Yes, the class of context-free languages is closed under intersection with regular languages..
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Yes, the class of context-free languages is closed under intersection with regular languages..
Nice... :) and how can I prove this?Could you give me an example?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
It is proved by combining a pushdown automaton and a deterministic finite automaton similarly to the proof that regular languages are closed under intersection. Namely, the set of states is the Cartesian product of the sets of the two automata, the accepting pairs are those where both states are accepting in their respective automata. Transitions are also done in the same way as in the given automata. That is, both automata are executed in parallel and accept only when both accept. This is described, for example, in Theorem 3.5.4 in "Elements of the Theory of Computation" by Lewis and Papadimitriou.

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
It is proved by combining a pushdown automaton and a deterministic finite automaton similarly to the proof that regular languages are closed under intersection. Namely, the set of states is the Cartesian product of the sets of the two automata, the accepting pairs are those where both states are accepting in their respective automata. Transitions are also done in the same way as in the given automata. That is, both automata are executed in parallel and accept only when both accept. This is described, for example, in Theorem 3.5.4 in "Elements of the Theory of Computation" by Lewis and Papadimitriou.

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

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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?
That's right.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
And what's about the language L-S?Is it also context-free and do I have to show it with the same way?
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.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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.
Nice,thank you very much!!! :) And...merry Christmas!!! ;)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
It is proved by combining a pushdown automaton and a deterministic finite automaton similarly to the proof that regular languages are closed under intersection. Namely, the set of states is the Cartesian product of the sets of the two automata, the accepting pairs are those where both states are accepting in their respective automata. Transitions are also done in the same way as in the given automata. That is, both automata are executed in parallel and accept only when both accept. This is described, for example, in Theorem 3.5.4 in "Elements of the Theory of Computation" by Lewis and Papadimitriou.

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

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Please describe the logic of 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?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Please describe the logic of 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?
From the image:
Ch_3_1.gif
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?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
the set of the regular languages is a proper subset of the set of the context-free languages.
This is true.
So,if we subtract the regular language from the context-free one,the set that remains is context-free.
And this is a completely different thing. The first quote talks about the difference between the set of context-free languages and the set of regular languages, and the second quote talks about the difference between an individual context-free language and an individual regular language.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
This is true.
And this is a completely different thing. The first quote talks about the difference between the set of context-free languages and the set of regular languages, and the second quote talks about the difference between an individual context-free language and an individual regular language.
I understand...Thanks a lot!!! :)