6.Closure Properties§

$L=\{a^nb^n | n>0\}$ , $LL = \{a^nb^na^mb^m | n>0, m>0 \}$

Theorem: CFL’s are closed under union, concatenation, and star-closure.

Given: 2 CFGs $G_1 = (V_1,T_1,S_1,P_1)$ and $G_2 = (V_2,T_2,S_2,P_2)$

Union

Construct G3 such that L(G3)=L(G1)∪L(G2).
G3=(V3,T3,S3,P3)
V3=V1∪V2∪{S3},T3=T1∪T2, and
P3=P1∪P2∪{S3→S1|S2}.

Construct G3 such that
L(G3)=L(G1)L(G2).
G3=(V3,T3,S3,P3)
V3=V1∪V2∪{S3},T3=T1∪T2, and
P3=P1∪P2∪{S3→S1S2}.

Construct G3 such that L(G3)=L(G1)∗
G3=(V3,T3,S3,P3)
V3=V1∪{S3},T3=T1, and
P3=P1∪P2∪{S3→S1S3|λ}.

Theorem: CFL’s are NOT closed under intersection

Let L1={anbncm|n,m>0} and
L2={anbmcm|n,m>0}
L1 and L2 are CFLs
Then L1∩L2={anbncn|n>0} is not CFL.

Theorem: CFL’s are NOT closed under complementation.

Set identity:

$L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$

Thus, CFLs are not closed under complementation.

L1={anbman∣m>0,n>0}
L2={w∣w∈Σ∗ and w has an even
number of b’s}, Σ={a,b},
L1∩L2={anbmbman} is a CFL.

CFL’s are closed under regular intersection. If $L_1$ is CFL and $L_2$ is regular, then $L_1 \cap L_2$ is CFL.

Proof: (sketch)

This proof is similar to the construction proof in which we showed regular languages are closed under intersection.

We can take a NPDA for

$L_1$ and a DFA for

$L_2$ and construct a NPDA for

$L_1 \cap L_2$ .

For a given CFG

$G$ , is

$L(G)$ empty?

A: Remove useless productions. Then, is

$S$ useless?

For a given CFG

$G$ , is

$L(G)$ infinite?

A: Is there a repeating variable?

For two given CFGs

$G_1$ and

$G_2$ , does

$L(G_1) = L(G_2)$ ?

A: There is no general algorithm that can always deterimine if two CFG generate the same language!

Here is a grammar for

$L = \{a^nb^nc^n \mid n \geq 1 \}$ .

S→abc∣aAbc
Ab→bA
Ac→Bbcc
bB→Bb
aB→aa∣aaA

Consider how to derive $a^3b^3c^3$

This is called a Context Sensitive Grammar