Closure Properties For Context
Closure Properties For Context
Closure Properties For Context
c
c
Union
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 -> 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.
Star
Suppose 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.
c c
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}.
cc
cc
c
Let 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.
c