Context-Free Language | Sahithyan's Notes

A language that can be generated by a CFG.

L(G) = \set{ x \in \Sigma^* \mid S \Rightarrow^* x }

A language $L$ is context-free iff there exists a CFG $G$ such that it generates $L$ . All regular languages are context-free.

Properties

If $L_1$ and $L_2$ are CFLs, then the following are also CFLs:

Union
$L_1 \cup L_2$ (using $S \to S_1 \mid S_2$ )
Concatenation
$L_1L_2$ (using $S \to S_1 S_2$ )
Kleene star
$L_1^*$ (using $S \to S_1 S \mid \varepsilon$ )

Intersection and complementation are not necessarily CFLs.

Intersection

$\{a^n b^n c^n \mid n \geq 0\}$ is not a CFL (pumping lemma for CFLs), yet it equals:

$\{a^n b^n c^m \mid n, m \geq 0\} \cap \{a^m b^n c^n \mid n, m \geq 0\}$

Both operands are CFLs. So CFLs are not closed under intersection.

Complementation

CFLs are closed under union. If they were also closed under complementation, De Morgan’s law gives:

$L_1 \cap L_2 = (L_1' \cup L_2')'$

Closure under both union and complementation would force closure under intersection. Since intersection is not closed, complementation is not closed.

Examples

Palindrome

Language of palindromes over $\Sigma = \set{a, b}$ . $\Lambda, a, b$ are palindromes.

If $x$ is palindrome then $axa$ and $bxb$ are palindromes.

S \rightarrow Λ\;|\;a\;|\;b\;|\;aSa\;|\;bSb

This language is not regular, but context-free.

a^n b^n

Language of strings with equal number of a’s followed by b’s.

Grammar:

S \rightarrow Λ\;|\;aSb

This language is not regular, but context-free.

a^n b^n c^n

Language of strings with equal number of a’s followed by b’s and c’s. Not context free. Intersection of 2 CFLs.

Syntax of Programming Languages

Programming languages (such as Python, Java) have syntax that can be described by CFGs. Used in compiler design to parse code and check for syntax errors.