Chapter 3 - Context-Free Languages

Table of Contents

1. Context Free Grammars (CFG)
2. Regular Languages are Context-free
3. Parse Trees
4. Pushdown Automata
5. Algorithmic Properties

1. Context Free Grammars (CFG)

Definition

A context-free grammar $G$ is a quadruple $(V, \Sigma, R, S)$ where:

• $V$ is an alphabet (set of all symbols)
• $\Sigma$ (the set of terminals) is a subset of $V$
  • Terminal symbols are the actual characters in the language (e.g., $a, b, x, +, *$)
• $R$ (the set of rules) is a finite subset of $(V - \Sigma) \times V^*$
  • Rules define how non-terminals can be replaced
• $S$ (the start symbol) is an element of $V - \Sigma$
  • This is where all derivations begin

Key Components:

• Non-terminals: Elements of $V - \Sigma$ (phrase types, variables)
  • These are symbols that can be further expanded
• Terminals: Elements of $\Sigma$ (actual symbols in strings)

Analogy: Think of a CFG like a recipe. Non-terminals are instructions like "add filling," while terminals are actual ingredients like "sugar" and "flour." The start symbol is "make cake," and rules tell you how to break down each instruction into smaller steps or actual ingredients.

Grammar Rules and Derivations

Notation:

• We write $\boxed{A \xrightarrow{G} u}$ for any rule $(A, u) \in R$
  • This means: "A generates u" or "A can be replaced by u"

Derivation:

• For any strings $\omega, \beta \in V^*$, we write $\boxed{\omega \underset{G}{\Rightarrow} \beta}$ if and only if:
  • There is a rule $A \xrightarrow{G} u$ in $R$
  • $\omega = xAy$ (string with $A$ somewhere in it)
  • $\beta = xuy$ (same string but $A$ replaced with $u$)

This means you can derive $\beta$ from $\omega$ by replacing one non-terminal with its production rule.

Multi-step Derivation:

• A sequence $\omega_0 \underset{G}{\Rightarrow} \omega_1 \underset{G}{\Rightarrow} ... \underset{G}{\Rightarrow} \omega_n$ where $n \geq 0$ is called a derivation of $\omega_n$ from $\omega_0$
• We write $\boxed{\omega \underset{G}{\Rightarrow}^* \beta}$ if there exists a derivation for $\beta$ from $\omega$
  • The asterisk * means "zero or more steps"

Language Generated by G:
$\boxed{L(G) = \{\omega \in \Sigma^* \mid S \underset{G}{\Rightarrow}^* \omega\}}$

• This is the set of all strings of terminal symbols that can be derived from the start symbol $S$

Exam Tip: When showing derivations, work step-by-step and replace only ONE non-terminal at a time. Make sure your final result contains only terminal symbols.

Example: Grammar for Arithmetic Expressions

Consider grammar $G = (V, \Sigma, R, E)$ where:

Terminals: $\Sigma = \{x, +, *, (, )\}$
Variables: $V = \Sigma \cup \{T, E, F\}$
Start Symbol: $E$ (Expression)

Rules $R$:

E → E + T    (Expression can be Expression plus Term)
E → T        (Expression can be just a Term)
T → T * F    (Term can be Term times Factor)
T → F        (Term can be just a Factor)
F → (E)      (Factor can be parenthesized Expression)
F → x        (Factor can be variable x)

Real-world use: This grammar structure is used in compilers to parse mathematical expressions in programming languages. The hierarchy (Expression → Term → Factor) enforces operator precedence: multiplication before addition.

Derivation Examples

Example 1: Derive $(x)$

Example 2: Derive $(x + x) * x$

Exam Strategy: Label which rule you're using at each step. This makes it easy for graders to follow your work and gives you partial credit even if you make a mistake later.

2. Regular Languages are Context-free

Theorem

$\boxed{\text{Any regular language is context-free}}$

Relationship: $\text{RL} \subseteq \text{CFL}$ (Regular Languages are a subset of Context-Free Languages)

This means CFGs are more powerful than regular expressions and finite automata. They can describe all regular languages PLUS more complex languages.

Proof (Converting FSA to CFG)

Given:

• A regular language $L$ accepted by a deterministic finite automaton $M = (K, \Sigma, \delta, s, F)$

Construct:

• A grammar $G = (V, \Sigma, R, S)$ as follows:

Construction:

1. $V = K \cup \Sigma$ (variables are the states plus terminals)
2. Start symbol $S$ = initial state of the DFA
3. Rules $R$ consist of:
   • $\boxed{P \to aQ}$ where $\delta(P, a) = Q$
     • For each transition from state $P$ to state $Q$ on symbol $a$
   • $\boxed{P \to \varepsilon}$ for $P \in F$
     • For each accepting state $P$

Example Conversion:

FSA Transition:     Grammar Rule:
[P] --a--> [Q]  →   P → aQ
[P] is accepting →   P → ε

Intuition: Each state becomes a non-terminal. Each transition becomes a rule that "consumes" a symbol and moves to the next state. Accepting states have rules that allow the derivation to terminate.

Proof Sketch:
By induction, we can show:

if and only if

Therefore, for any string $\omega \in \Sigma^*$:

• $\omega \in L$
• ⟺ $(S, \omega) \vdash_M^* (P, \varepsilon)$ and $P \in F$
• ⟺ $S \Rightarrow^* \omega P$ and $P \to \varepsilon$ in $R$
• ⟺ $S \Rightarrow^* \omega$

Example CFGs for Non-Regular Languages

Example 1: $L = \{a^nb^n \mid n \geq 0\}$

This language is NOT regular (it requires counting/memory), but it IS context-free.

Grammar:

S → ab
S → aSb
S → ε

Derivation for $aabb$:

Real-world application: This pattern appears in matching opening and closing brackets in code: (), ((())), etc.

Example 2: $L = \{a^nb^nc^n \mid n \geq 0\}$

This language is NOT context-free (requires counting two independent counters simultaneously).

3. Parse Trees (Derivation Trees)

Definition

A parse tree (or derivation tree) is a graphical representation of a derivation.

Structure:

• Root: The start symbol or a non-terminal
• Internal nodes: Non-terminal symbols
• Leaves: Terminal symbols or $\varepsilon$
• Yield: The string formed by reading leaves from left to right

Construction Rules for Parse Trees

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

Rule 1: Terminal Symbols

For each $a \in \Sigma$, the tree:

  a

is a parse tree with:

• Root: $a$
• Only leaf: $a$
• Yield: $a$

Rule 2: Epsilon Rules

If $A \to \varepsilon$ is a rule in $G$, then:

  A
  |
  ε

is a parse tree with:

• Root: $A$
• Only leaf: $\varepsilon$
• Yield: $\varepsilon$

Rule 3: Multiple Children

If $T_1, T_2, ..., T_n$ are parse trees (where $n \geq 1$) with:

• Roots: $A_1, ..., A_n$
• Yields: $y_1, ..., y_n$

And $A \to A_1...A_n$ is a rule in $R$, then:

      A
     /|\
    / | \
   A₁ A₂ Aₙ
   |  |  |
  T₁ T₂ Tₙ

is a parse tree with:

• Root: $A$
• Leaves: All leaves of $T_1, ..., T_n$
• Yield: $y_1...y_n$

Parse Tree Examples

Example 1: Parse tree for $(x)$

        E
        |
        T
        |
        F
       /|\
      ( E )
        |
        T
        |
        F
        |
        x

Yield: $(x)$

Example 2: Grammar for $\{a^nb^n\}$

Grammar:

S → ab
S → aSb

Parse tree for $aaabbb$:

       S
      /|\
     a S b
      /|\
     a S b
      /|\
     a S b
       |
       ε

Yield: $aaabbb$

Exam Tip: Always verify your parse tree by reading the leaves from left to right - this should give you your target string.

Key Lemma

Theorem: Let $G = (V, \Sigma, R, S)$ be a context-free grammar, $A \in V - \Sigma$, and $\omega \in \Sigma^*$.

The following statements are logically equivalent:

1. $\boxed{A \underset{G}{\Rightarrow}^* \omega}$
2. There exists a parse tree with root $A$ and yield $\omega$

This means: Derivations and parse trees are two ways of representing the same thing. A derivation is the "process" and a parse tree is the "structure."

4. Left-most and Right-most Derivations

Left-most Derivation

Definition: We write $x \underset{L}{\Rightarrow} y$ if the non-terminal symbol being replaced is the leftmost non-terminal in the string.

• $x = \omega A\beta$
• $y = \omega u\beta$
• where $\omega \in \Sigma^*$, $\beta \in V^*$, and $A \to u$ is a rule in $R$

Form: $x_1 \underset{L}{\Rightarrow} x_2 \underset{L}{\Rightarrow} ... \underset{L}{\Rightarrow} x_n$

Example: $E \underset{L}{\Rightarrow} ... \underset{L}{\Rightarrow} (x+x)*x$

Right-most Derivation

Definition: We write $x \underset{R}{\Rightarrow} y$ if the non-terminal symbol being replaced is the rightmost non-terminal in the string.

• $x = \omega A\beta$
• $y = \omega u\beta$
• where $\beta \in \Sigma^*$, $\omega \in V^*$, and $A \to u$ is a rule in $R$

Form: $x_1 \underset{R}{\Rightarrow} x_2 \underset{R}{\Rightarrow} ... \underset{R}{\Rightarrow} x_n$

Example: $E \underset{R}{\Rightarrow} ... \underset{R}{\Rightarrow} (x+x)*x$

Key Insight: The ORDER of applying derivation rules doesn't matter for the final result, but it creates a different "path" through the derivation. Left-most and right-most are standard conventions used by parsers.

Equivalence Theorem

Theorem: Let $G = (V, \Sigma, R, S)$ be a context-free grammar, $A \in V - \Sigma$, and $\omega \in \Sigma^*$.

The following statements are equivalent:

1. $\boxed{A \underset{G}{\Rightarrow}^* \omega}$ (some derivation exists)
2. There is a parse tree with root $A$ and yield $\omega$
3. $\boxed{A \underset{L}{\Rightarrow}^* \omega}$ (left-most derivation exists)
4. $\boxed{A \underset{R}{\Rightarrow}^* \omega}$ (right-most derivation exists)

Meaning: No matter which order you apply the rules (left-most, right-most, or random), you'll get the same parse tree and same final string. The derivation path differs, but the result is the same.

Exam Application: You can choose whichever derivation order is easiest for you! Left-most is often more intuitive.

5. Ambiguity

Ambiguous vs Unambiguous Grammars

Let $\Sigma = \{x, +, *, (, )\}$. Consider two grammars for the same language:

Grammar G₁ (Unambiguous)

V₁ = Σ ∪ {T, F, E}
R₁ = {
    E → E + T
    E → T
    T → T * F
    T → F
    F → (E)
    F → x
}

Property: For each string $\omega \in L(G_1)$, there is exactly one parse tree that yields $\omega$.

Parse tree for $x + x * x$:

        E
       /|\
      E + T
      |  /|\
      T T * F
      | |   |
      F F   x
      | |
      x x

This correctly shows that multiplication happens before addition.

Grammar G₂ (Ambiguous)

V₂ = Σ ∪ {E}
R₂ = {
    E → E + E
    E → E * E
    E → (E)
    E → x
}

Property: There are distinct parse trees yielding the same string.

Two different parse trees for $x + x * x$:

Tree 1 (multiplication first):

      E
     /|\
    E + E
    |  /|\
    x E * E
      |   |
      x   x

Tree 2 (addition first):

      E
     /|\
    E * E
   /|\  |
  E + E x
  |   |
  x   x

Problem: Ambiguity means the grammar doesn't uniquely determine how to parse an expression, leading to potential misinterpretation of meaning.

Definition of Ambiguity

A grammar $G$ is ambiguous if:
$\boxed{\exists \omega \in L(G) \text{ such that } \omega \text{ has more than one parse tree}}$

A grammar is unambiguous if:
$\boxed{\forall \omega \in L(G), \omega \text{ has exactly one parse tree}}$

Real-world Impact: Programming language compilers need unambiguous grammars. Otherwise, the same code could be interpreted different ways, leading to bugs and security vulnerabilities.

Spotting Ambiguity

How to identify ambiguous grammars:

1. Look for recursive rules on both sides:
   • $E \to E + E$ (both left and right are the same non-terminal)
   • This creates multiple ways to group operations
2. Missing operator precedence rules:
   • When all operators are at the same level in the grammar
   • Example: $E \to E + E \mid E * E$ treats $+$ and $*$ equally
3. No associativity specification:
   • $E \to E + E$ doesn't specify left or right associativity
   • Can parse $x + x + x$ as $(x+x)+x$ or $x+(x+x)$

Common culprits:

E → E + E       // Ambiguous (left or right associative?)
E → E * E       // Ambiguous (same issue)
E → (E)
E → x

How to fix:

E → E + T       // Unambiguous (forces left associativity for +)
E → T
T → T * F       // Unambiguous (forces left associativity for *)
T → F
F → (E)
F → x

The hierarchy $E \to T \to F$ enforces precedence: $*$ binds tighter than $+$.

Exam Tip: If asked "What makes this grammar ambiguous?", look for rules like $A \to A \circ A$ where the same non-terminal appears on both sides of an operator.

Summary & Key Takeaways

Context-Free Grammars

• Definition: $G = (V, \Sigma, R, S)$
  • More powerful than regular expressions
  • Can handle nested structures (balanced parentheses, etc.)

Key Relationships

• Regular Languages ⊂ Context-Free Languages ⊂ All Languages
• Any FSA can be converted to an equivalent CFG
• Not all CFLs are regular (e.g., $\{a^nb^n\}$)

Derivations & Parse Trees

• Derivation: Step-by-step application of rules
• Parse Tree: Graphical representation of structure
• Equivalence: Any derivation corresponds to exactly one parse tree (if unambiguous)

Left-most vs Right-most

• Different paths to the same result
• Useful for parser implementation
• Don't affect final yield or parse tree structure

Ambiguity

• Critical for compilers: Need unambiguous grammars
• Detection: Look for symmetric recursion ($E \to E \circ E$)
• Resolution: Introduce hierarchy and enforce precedence

Exam Tips Summary

1. For derivations: Work step-by-step, label rules used
2. For parse trees: Verify yield by reading leaves left-to-right
3. For ambiguity questions: Look for recursive rules and lack of precedence
4. For conversions: FSA → CFG is straightforward (states become non-terminals)
5. Time management: Start with simpler derivations, come back to complex ones

Real-World Applications

Compilers & Programming Languages

• Parsing source code syntax
• Enforcing operator precedence
• Checking balanced brackets, parentheses

Natural Language Processing

• Parsing sentence structure
• Grammar checking
• Machine translation

Data Formats

• XML/HTML parsing
• JSON validation
• Configuration file parsing

Protocol Design

• Network protocol specification
• API definition languages
• Communication format standards

Additional Practice Problems

Problem 1

Design a CFG for $L = \{a^ib^jc^k \mid i = j \text{ or } j = k\}$

Problem 2

Prove that $L = \{a^nb^nc^n \mid n \geq 0\}$ is NOT context-free (requires Pumping Lemma for CFLs)

Problem 3

Convert the following NFA to a CFG:

• States: $\{q_0, q_1\}$
• Initial: $q_0$
• Accepting: $\{q_1\}$
• Transitions: $\delta(q_0, a) = q_1$, $\delta(q_1, b) = q_1$

Problem 4

Show that the following grammar is ambiguous and provide an unambiguous equivalent:

S → aSb | SS | ε