Designing Context-Free Grammers

Designing a Context-Free Grammar (CFG) is really about thinking recursively and breaking a language into smaller, replaceable parts.

Here’s a step-by-step method explaining how to design CFGs.

---

1. Understand the Structure of the Language

• Identify patterns in the strings you want to generate.

• Look for recursion or nesting (these are strong hints that the language is context-free).

• Ask: “What must always match or balance?”

Example 1:
Balanced a’s and b’s: $\{ a^n b^n \ | \ n \ge 0 \}$

• Pattern: Same number of a’s followed by same number of b’s.

• Recursive idea: If aabb is in the language, then so is aa…bb with more pairs.

---

2. Choose Nonterminals for Main Components

• Start with S (start symbol).

• If the language has subparts, create separate variables for them.

Example 2:
Arithmetic expressions might need:

$$V = \{ E, T, F \}$$

where E = expression, T = term, F = factor.

---

3. Write Productions that Capture the Pattern

• Recursive productions handle repetition/nesting.

• Base cases handle the simplest strings.

Example 1 grammar for $a^n b^n$:

$$S \rightarrow aSb \ | \ \varepsilon$$

• Recursive case: a + (another S) + b

• Base case: empty string.

---

4. Test Small Strings

• Generate the shortest strings.

• Check if all valid strings are generated.

• Ensure no invalid strings appear.

Example:
For $S \rightarrow aSb \ | \ \varepsilon$

• $\varepsilon$ ✅

• ab ✅

• aabb ✅

• No abb or aab appears ✅

---

5. Handle Choices and Branches

• Use the “$|$” option in rules for alternatives.

Example 3: Palindromes over {a, b}:

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

This allows:

• Recursion with matching ends.

• Base cases of length 0 or 1.

---

6. Avoid Ambiguity if Needed

• If parsing needs to be unique (like in programming languages), rewrite rules to enforce precedence and associativity.

Example (unambiguous arithmetic):

$$E \rightarrow E + T \ | \ T$$
$$T \rightarrow T * F \ | \ F$$
$$F \rightarrow (E) \ | \ id$$

---

7. Think in Terms of “Generate, Not Recognize”

• A CFG describes how to build strings, not just check them.

• This “construction mindset” makes design easier.

---

✅ Summary Table for Designing CFGs

Step	What to Do	Example
1	Identify structure	Equal a’s and b’s
2	Choose variables	S
3	Write recursion + base	S → aSb | ε
4	Test small cases	ε, ab, aabb
5	Add choices	S → aSa | bSb | a | b | ε
6	Resolve ambiguity if needed	Separate precedence levels
7	Check completeness	Generate all valid strings

Examples

1. Balanced Parentheses

Language:

$$L = \{ \text{all correctly balanced parentheses strings} \}$$

Alphabet: $\Sigma = \{ (, ) \}$

Step 1 — Structure

• A balanced string can be empty.

• If x is balanced, then (x) is balanced.

• If x and y are balanced, then xy is balanced.

Step 2 — Variables
$V = \{ S \}$

Step 3 — Rules

$$S \rightarrow (S)S \ | \ \varepsilon$$

Step 4 — Test

• ε ✅

• () ✅ (S → (S) S → (ε)

• (()) ✅

• ()() ✅

---

2. Palindromes

Language:

$$L = \{ w \in \{a, b\}^* \ | \ w = w^R \}$$

Step 1 — Structure

• Palindrome can be empty or single letter.

• If P is palindrome, then aPa and bPb are palindromes.

Step 2 — Variables
$V = \{ S \}$

Step 3 — Rules

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

Step 4 — Test

• ε ✅

• a ✅

• b ✅

• aba ✅

• abba ✅

---

3. Arithmetic Expressions with Precedence

Language: expressions with + and * over identifiers id, where * has higher precedence.

Step 1 — Structure

• Expression = terms joined by +

• Term = factors joined by *

• Factor = identifier or parenthesized expression.

Step 2 — Variables
$V = \{ E, T, F \}$

Step 3 — Rules

$$E \rightarrow E + T \ | \ T$$
$$T \rightarrow T * F \ | \ F$$
$$F \rightarrow (E) \ | \ id$$

Step 4 — Test

• id ✅

• id + id ✅

• id * id + id ✅

• id + id * id ✅ (multiplication grouped first)

---

4. Equal Number of 0’s and 1’s (not necessarily grouped)

Language:

$$L = \{ w \in \{0,1\}^* \ | \ \#0(w) = \#1(w) \}$$

Step 1 — Structure
This is a non-regular but context-free language.
A string can start with:

• 0, end with 1, and middle balanced.

• 1, end with 0, and middle balanced.

• Two balanced strings concatenated.

Step 2 — Variables
$V = \{ S \}$

Step 3 — Rules

$$S \rightarrow 0S1 \ | \ 1S0 \ | \ SS \ | \ \varepsilon$$

Step 4 — Test

• ε ✅

• 01 ✅

• 10 ✅

• 0110 ✅

• 1100 ✅

• 1010 ✅

---

5. Simple If-Else Statements

Language:

$$\text{if <cond> then <stmt> else <stmt>}$$

and

$$\text{if <cond> then <stmt>}$$

Step 1 — Structure
We must allow both forms and avoid ambiguity (dangling else problem).
We use matched and unmatched statements.

Step 2 — Variables
$V = \{ S, M, U \}$

• $M$= matched if-else

• $U$ = unmatched if

Step 3 — Rules
Matched statements:

$$M \rightarrow \text{if C then M else M} \ | \ \text{other}$$

Unmatched statements:

$$U \rightarrow \text{if C then S} \ | \ \text{if C then M else U}$$

Statement:

$$S \rightarrow M \ | \ U$$

Here "other" = any non-if statement, "C" = condition.

Step 4 — Test

• if C then other ✅

• if C then other else other ✅

• if C then if C then other else other ✅ (correct nesting)