This page summarizes closure properties for context-free languages. Our earlier handout on regular languages covered the basic idea of closure and how to use closure properties to prove non-regularity. Everything is very similar for context-free languages, except that they aren't closed under as wide a range of operations. Show Closure propertiesContext-free languages are closed under several common operations. UnionSuppose we have grammars for two languages, with start symbols S and T. Rename variables as needed to ensure that the two grammars don't share any variables. Then construct a grammar for the union of the languages, with start symbol Z, by taking all the rules from both grammars and adding a new rule Z -> S | T. Concatenation Suppose we have grammars for two languages, with start symbols S and T. Rename variables as needed to ensure that the two grammars don't share any variables. Then construct a grammar for the union of the languages, with start symbol Z, by taking all the rules from both grammars and adding a new rule Z -> ST. StarSuppose that we have a grammar for the language L, with start symbol S. The grammar for L*, with start symbol T, contains all the rules from the original grammar plus the rule T -> TS | ε. String reversal Reverse the character string on the righthand side of every rule in the grammar. Homomorphism Suppose that we have a grammar G for language L and a homomorphism h. To construct a grammar for h(L), modify the righthand side of every rule in G to replace each terminal symbol t with its image h(t) under the homomorphism. Intersection with a regular language The intersection of a context-free language and a regular language is always context-free. To show this, assume we have a PDA M accepting the context-free language and a DFA N accepting the regular language. Use the product construction to create a PDA which simulates both machines in parallel. This works because only M needs to manipulate the stack; N never touches the stack. Non-closure factsContext-free languages are not closed under set intersection or set complement. Intersection Consider the languages L1 and L2 defined by L1 = {anbncj: n,j ≥ 0} and L2 = {ajbncn: n,j ≥ 0}. They are both context-free. However, their intersection is the language L = {anbncn: n ≥ 0}. We used the pumping lemma to show that L is not context-free. Set complement There are two approaches to showing this. First, you can use deMorgan's laws to show that closure under set complement plus closure under union would imply closure under intersection. Like regular languages, context-free languages are not closed under the subset/superset relationship. For example, a*b*c* is context-free (in fact regular), but contains the non-context-free subset anbncn. And anbncn contains the context-free subset {abc, aabbcc, aaabbbccc}. Sample proof using closure propertiesLet L={w in {a,b,c}* with equal numbers of a's, b's, and c's}. L is not context-free. To show this, suppose L were context free. Consider L' = L ∩ a*b*c*. Because context-free languages are closed under intersection with regular languages, L' must be regular. But L' is just anbncn, which we know not to be regular. So we must have been wrong in our assumption that L was regular. Context-free languages are closed under −
UnionLet L1 and L2 be two context free languages. Then L1 ∪ L2 is also context free. ExampleLet L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm } The corresponding grammar G will have the additional production S → S1 | S2 ConcatenationIf L1 and L2 are context free languages, then L1L2 is also context free. ExampleUnion of the languages L1 and L2, L = L1L2 = { anbncmdm } The corresponding grammar G will have the additional production S → S1 S2 Kleene StarIf L is a context free language, then L* is also context free. ExampleLet L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε Kleene Star L1 = { anbn }* The corresponding grammar G1 will have additional productions S1 → SS1 | ε Context-free languages are not closed under −
What are the closure properties of context free languages?What are Context Free Language Closure Properties?. Union.. Concatenation.. Kleene Star Operation.. How do you prove closure language?Regular Languages are closed under complementation, i.e., if L is regular then L = Σ∗ \ L is also regular. Proof. If L is regular, then there is a DFA M = (Q,Σ, δ, q0,F) such that L = L(M). Then, M = (Q,Σ, δ, q0,Q \ F) (i.e., switch accept and non-accept states) accepts L.
How do you prove something is a CFL?We can prove that a language is context-free if we construct a context-free grammar that generates it. Alternatively, we can create a pushdown automaton that recognizes the language. On the other hand, we use Ogden's lemma and the pumping lemma for context-free languages to prove that a language isn't context-free.
What are the different closure properties of CFL explain with example?Example. The CFLs do not get closed under the following: Intersection − In case L1 and L2 are CFLs, then the L1 ∩ L2 is not context-free. Intersection with regular language − In case L1 happens to be a regular language, while L2 is a CFL, then L1 ∩ L2 would be a CFL.
|