Processing math: 100%

Partial Coursenotes for Formal Languages and Automata

Chapter 7 Week 9

| About « 7.1. Pumping Lemma for CFL :: Contents :: 8.1. Turing Machines »

7.2. Closure Properties for CFLs¶

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

7.2.2. Union¶

Construct $G_3$ such that $L(G_3) = L(G_1) \cup L(G_2)$ .

$G_3 = (V_3,T_3,S_3,P_3)$

$V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2$ , and $P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1 | S_2 \}$ .

7.2.3. Concatenation¶

Construct $G_3$ such that $L(G_3) = L(G_1)L(G_2)$ .

$G_3 = (V_3,T_3,S_3,P_3)$

$V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2$ , and $P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_2 \}$ .

7.2.4. Star-Closure¶

Construct $G_3$ such that $L(G_3) = L(G_1)^*$

$G_3 = (V_3,T_3,S_3,P_3)$

$V_3 = V_1 \cup \{S_3\}, T_3 = T_1$ , and $P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_3|\lambda \}$ .

7.2.5. Intersection¶

Theorem: CFL’s are NOT closed under intersection

Let $L_1 = \{a^nb^nc^m | n,m > 0\}$ and $L_2 = \{a^nb^mc^m | n,m> 0\}$

$L_1$ and $L_2$ are CFLs

Then $L_1 \cap L_2 = \{a^nb^nc^n | n >0 \}$ is not CFL.

7.2.6. Complementation¶

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.

7.2.7. Example for theorem below:¶

$L_1 = \{a^nb^ma^n \mid m> 0, n>0 \}$

$L_2 = \{w \mid w \in{\Sigma}^{*}$ and $w$ has an even number of b’s}, $\Sigma = \{a,b\}$ ,

$L_1 \cap L_2 = \{a^nb^mb^ma^n\}$ is a CFL.

7.2.8. Regular Intersection (1)¶

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.

7.2.9. Some Decision Problems for CFGs¶

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!

7.2.10. A Richer Grammar¶

Here is a grammar for $L = \{a^nb^nc^n \mid n \geq 1 \}$ .

$S \rightarrow abc \mid aAbc$

$Ab \rightarrow bA$

$Ac \rightarrow Bbcc$

$bB \rightarrow Bb$

$aB \rightarrow aa \mid aaA$

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

This is called a Context Sensitive Grammar

Contact Us || Privacy | | License « 7.1. Pumping Lemma for CFL :: Contents :: 8.1. Turing Machines »