Context-Free Langs: S-L Check if Not CF?

  • MHB
  • Thread starter evinda
  • Start date
In summary: 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 also context-free?The closure property of intersection says that if S and L are both context-free languages, then the language S-L is also context-free.
  • #1
evinda
Gold Member
MHB
3,836
0
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?
 
Technology news on Phys.org
  • #2
evinda said:
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?
 
  • #3
evinda said:
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..
 
  • #4
Evgeny.Makarov said:
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?
 
  • #5
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).
 
  • #6
Evgeny.Makarov said:
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?
 
  • #7
evinda said:
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.
 
  • #8
Evgeny.Makarov said:
That's right.

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?
 
  • #9
evinda said:
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.
 
  • #10
Evgeny.Makarov said:
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! ;)
 
  • #11
evinda said:
And...merry Christmas! ;)
Merci! And same to you!
 
  • #12
Evgeny.Makarov said:
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?
 
  • #13
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?
 
  • #14
Evgeny.Makarov said:
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:
View attachment 1850
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?
 

Attachments

  • Ch_3_1.gif
    Ch_3_1.gif
    2.8 KB · Views: 73
  • #15
evinda said:
the set of the regular languages is a proper subset of the set of the context-free languages.
This is true.
evinda said:
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.
 
  • #16
Evgeny.Makarov said:
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! :)
 

FAQ: Context-Free Langs: S-L Check if Not CF?

What is a context-free language?

A context-free language is a type of formal language that can be described by a context-free grammar, which is a set of production rules that define the language's syntax. Context-free languages are used in computer science and linguistics to describe and analyze the structure of languages.

What does S-L Check if Not CF mean?

S-L Check if Not CF stands for the "stack and lookahead check if not context-free" algorithm. It is a method used to determine if a given language is not context-free, also known as a non-context-free language. This algorithm is used to prove that a language is not context-free by showing that it cannot be generated by a context-free grammar.

How does the S-L Check if Not CF algorithm work?

The S-L Check if Not CF algorithm works by simulating the operation of a pushdown automaton, a type of finite state machine that can recognize context-free languages. The algorithm uses a stack and a lookahead symbol to check if a string of symbols can be generated by a context-free grammar. If the algorithm reaches a point where it cannot continue, it means that the language is not context-free.

What are some examples of non-context-free languages?

Some examples of non-context-free languages include the language of palindromes, the language of balanced parentheses, and the language of nested parentheses. These languages cannot be generated by a context-free grammar because they require an infinite number of states to recognize them.

Why is it important to check if a language is not context-free?

It is important to check if a language is not context-free because context-free languages have many useful properties, such as being easily parsable by computers and having a well-defined syntax. However, not all languages can be described by a context-free grammar, and knowing that a language is not context-free can help in designing more efficient algorithms for recognizing and processing it.

Similar threads

MHB Prove that if L is regular, then L^R is regular
Replies
1
Views
2K
MHB Show that the language is not context-free with the Pumping Lemma
Replies
6
Views
5K
MHB Regular and Context-free languages
Replies
2
Views
2K
MHB Find the context-free grammar,that produces a language
Replies
14
Views
4K
MHB Determine if the string is in L(G)
Replies
2
Views
1K
Automata theory: understanding different automata
Replies
4
Views
4K
MHB {a^k,k is a prime is not contextfree}
Replies
6
Views
2K
Python How to resize and save a slice from a nii file as a PNG image in Python?
Replies
3
Views
2K
MHB What Language Does This Specific Grammar Produce?
Replies
1
Views
1K
MHB Can You Convert a Context-Free Grammar to a Deterministic One?
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top