6 Context Free Grammars🔗

While REs or DFAs can describe simple patterns, CFGs can describe nested or hierarchical structures — such as balanced parentheses or matching numbers of symbols (e.g., aⁿbⁿ).

6.1 Formal Definition🔗

G=(N,Σ,P,S)

6.1.1 Example 1: CFG for a* | b*🔗

Grammar:

S → A | B
A → aA | ε
B → bB | ε

Example derivation: To generate the string aaa:

S → A
A → aA
A → aaA
A → aaaA
A → aaa

The process of generating a string from the start symbol using production rules is called a derivation. Finding such a derivation is called parsing.

6.1.2 Example 2: Palindromes over {a, b}🔗

A palindrome reads the same forward and backward.

Grammar:

S → aSa | bSb | a | b | ε

To generate aababaa:

S → aSa
S → a aS a a
S → a a b S b a a
S → a a b a b a a

6.1.3 Example 3: Balanced a’s and b’s (aⁿbⁿ)🔗

Language: { ε, ab, aabb, aaabbb, … }

Grammar:

S → aSb | ε

S → ε             (n = 0)
S → aSb → ab      (n = 1)
S → aSb → aaSbb → aaabbb   (n = 3)

6.1.4 Example 4: aⁿb²ⁿ🔗

This means: for every a, there are two b’s.

Grammar:

S → aSbb | ε

S → aSbb → aaSbbbb → aabbbb

6.1.5 Arithmetic Expressions🔗

To describe expressions like (1+2)*4 or 1-2-3:

E → E + E | E - E | E * E | (E) | 1 | 2 | 3

Valid strings:

(1+2)
1+2+4
1-2*4
(1+2)*4

1++2
(1+
2**4

Example Derivation: Expression (2+3)*4

E → E * E
→ (E) * E
→ (E + E) * E
→ (2 + E) * E
→ (2 + 3) * E
→ (2 + 3) * 4

6.1.6 Leftmost Derivation🔗

In a leftmost derivation, always expand the leftmost non-terminal first.

Example grammar:

S → AB
A → aA | ε
B → bB | ε

Derivation for ab:(Leftmost non-terminal expanded each time.)

S → AB → aAB → aB → abB → ab

6.1.7 Parse Tree🔗

        S
       /|\
      a S bb
        |
        ε

6.1.8 CFG Limitations🔗

CFGs cannot describe some languages, such as:

{ aⁿ bⁿ cⁿ | n ≥ 1 }