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$
Concatenation
$L_1L_2$
Kleene star
$L_1^*$

The following are not necessarily CFLs:

Intersection
$L_1 \cap L_2$
Complementation
$L_1'$

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.

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.