Formal definition of Context-Free Grammer

 Here’s the formal definition of a Context-Free Grammar (CFG).

---

Definition

A Context-Free Grammar is a 4-tuple:

$$G = (V, \Sigma, R, S)$$

where:

1. $V$ — A finite set of nonterminal symbols (or variables).

2. $\Sigma$ — A finite set of terminal symbols, such that $V \cap \Sigma = \varnothing$
   

3. $R$ — A finite set of production rules of the form

   $$A \rightarrow \alpha$$
   

   where $A \in V$ and $\alpha \in (V \cup \Sigma)^*$ (that is, $\alpha$

    is any finite string of terminals and/or nonterminals, possibly empty).

4. $S$ — A distinguished element of $V$, called the start symbol.

---

✅ Key condition that makes it “context-free”:
In every production $A \rightarrow \alpha$, the left-hand side consists of exactly one nonterminal symbol $A$.

Characteristics of CFGs

• Each production’s LHS must be a single nonterminal (unlike context-sensitive grammars).

• They can describe nested and recursive structures, which are impossible for regular grammars.

• Languages generated by CFGs are called Context-Free Languages (CFLs).

Example

Let:

• $V=\{S\}$

• $\Sigma = \{a, b\}$
  

• $R: S \rightarrow aSb \ | \ \varepsilon$
  

• $S$ is the start symbol.

This grammar generates strings with equal numbers of a’s followed by b’s:

$$L = \{ a^n b^n \ | \ n \ge 0 \}$$

Derivation example:

$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aa\varepsilon bb = aabb$$

Parse Trees

A parse tree shows how a string is generated from the start symbol.

For the earlier grammar 

$S \rightarrow aSb \ | \  \varepsilon$, the string "aabb" has:
        S
       /|\
      a S b
        /|\
       a S b
         |
         ε

A Worked Example

Problem: Create a CFG for

$$L = \{ w \in \{a, b\}^* \ | \ w \text{ is a palindrome} \}$$

Solution:

$$S \rightarrow aSa \ | \ bSb \ | \ a \ | \ b \ | \ \varepsilon$$

Derivation for "abba":

$$S \Rightarrow aSa \Rightarrow abSb a \Rightarrow ab\varepsilon b a = abba$$