Designing Context-Free Grammars

1. The Core Strategy: Recursive Design

The most effective way to design a CFG is to think about the language's structure recursively. For any given language, ask yourself two questions:

1. What are the smallest possible strings in this language? These will form your base cases, which are typically handled by rules that produce terminals or the empty string, $\epsilon$. This is the termination condition for your recursion.
2. How can I build larger strings in the language from smaller strings already in the language? This will inform your recursive rules, where a non-terminal appears on both the left and right side of a production.

Let's apply this strategy to some fundamental language patterns.

2. Pattern 1: Matching Symmetric Symbols

Many context-free languages involve some form of symmetry or matching of symbols from the outside in. The canonical example is the language $L=\{a^n{b}^n\mid n\ge 0\}$.

• Base Case: The smallest string is for $n=0$, which is $\epsilon$.
• Recursive Step: If we have a string $w=a^k{b}^k$ that is already in the language, we can create a new, larger string by wrapping it with an a at the front and a b at the end: a$w$b = $a^{k+1}{b}^{k+1}$.

This logic translates directly into the following grammar, where S is the start symbol:

• $S\to aSb$ (Recursive step)
• $S\to \epsilon$ (Base case)

The following video provides a concise walkthrough of this example and others, which will serve as our guide for several patterns in this lesson.

Palindromes: A Generalization of Symmetry

A palindrome is a string that reads the same forwards and backwards (e.g., racecar). This is a generalization of the a^n b^n pattern. Let's design a CFG for the language of all palindromes over the alphabet $\Sigma =\{0,1\}$.

• Recursive Step: If a string w is a palindrome, then 0w0 and 1w1 are also palindromes.
• Base Cases: What are the smallest palindromes? The empty string ($\epsilon$) is a palindrome (for even-length cases). The single characters 0 and 1 are also palindromes (for odd-length cases).

This gives us the grammar:
$S\to 0S0\mid 1S1\mid 0\mid 1\mid \epsilon$

The video below explains this construction very clearly.

To solidify this, here is a visual breakdown of how this grammar generates both even and odd length palindromes.

3. Pattern 2: Sequential and Nested Structures

Not all languages are built from the outside in. Some are built by concatenating valid strings or nesting them. The classic example is the language of balanced parentheses.

A string of parentheses is balanced if:

1. It is the empty string. (Base Case)
2. It is of the form (w), where w is a balanced string. (Nesting)
3. It is of the form xy, where x and y are both balanced strings. (Concatenation)

This definition leads to the grammar:
$S\to (S)\mid SS\mid \epsilon$

As we discussed in the previous lesson, the S -> SS rule makes this grammar ambiguous. For example, the string ()() has two different leftmost derivations. While correct, this ambiguity is often undesirable. An alternative, unambiguous grammar for the same language is:
$S\to (S)S\mid \epsilon$
This version generates a balanced string (S) and then, optionally, another balanced string S immediately after it, avoiding the ambiguity of the SS rule.

The following video segment discusses the balanced parentheses problem and highlights the ambiguity issue.

4. Pattern 3: Advanced Composition Techniques

More complex languages often require combining these basic patterns. This is where using multiple non-terminals becomes essential. You can think of non-terminals as "helper functions" or "subroutines" that are responsible for generating a specific part of the language.

Chaining Variables for Sequential Dependencies

Consider the language $L=\{a^i{b}^j{c}^k\mid i+j=k,\text{ and }i,j,k\ge 0\}$. Here, every a and every b must be matched by a c. The a's come before the b's.

We can't use a single symmetric rule. The solution is to handle the a's first, then hand off to another variable to handle the b's.

1. Generate a's and c's symmetrically: S -> aSc.
2. Once all a's are generated, switch to a new non-terminal, let's call it B, to generate b's and c's symmetrically.
3. The base case is ε.

This gives the grammar:

• $S\to aSc\mid B$ (Match an a with a c, or switch to matching b's)
• $B\to bBc\mid \epsilon$ (Match a b with a c, or terminate)

Watch the following clip to see this technique in action.

Other Powerful Techniques

The "15 Examples" video contains several other excellent patterns. I encourage you to watch these short clips to add more tools to your CFG design toolkit.

Conclusion

In this lesson, we moved from analyzing grammars to designing them. We saw that building a CFG is a recursive process that involves identifying base cases and recursive rules for generating larger strings.

Key Takeaways:

• Recursive Design: The core strategy is to define a language in terms of itself. Find the smallest strings (base cases) and figure out how to build larger strings from smaller ones (recursive steps).
• Symmetric Matching: For languages like aⁿbⁿ and palindromes, use rules like $S\to aSb$ to build from the outside in.
• Sequential/Nested Structures: For languages like balanced parentheses, rules like $S\to (S)S$ can generate nested and concatenated strings.
• Composition with Helper Variables: For complex languages, use different non-terminals as subroutines to handle different parts of the string, such as chaining them for sequential dependencies ($S\to aSc\mid B$) or combining them for logical 'OR' conditions ($S\to A\mid B$).

Preview of the Next Lesson:
Our design process can sometimes lead to grammars that are overly complex, containing redundant or useless rules. Before we can use these grammars in practical applications like parsing, we need to clean them up. In the next lesson, we will learn about algorithms to simplify CFGs by removing useless symbols, $\epsilon$-productions, and unit productions. This "grammar hygiene" is an essential step in the formal language toolkit.