Context-Free Grammars & Classification

Definition

A Context-Free Grammar (CFG) is a 4-tuple (V, T, P, S) — non-terminals, terminals, production rules, start symbol — used to define the syntax of programming languages (more expressive than regular grammars; can express nested/recursive structures like matched parentheses).

Key Points

• Why not regular expressions for syntax? Regex/FA cannot count or match nested structures (e.g., balanced brackets) — CFGs can, via recursive production rules.
• Chomsky Hierarchy (classification by generative power): Type 0 (unrestricted) ⊃ Type 1 (context-sensitive) ⊃ Type 2 (context-free) ⊃ Type 3 (regular). Programming language syntax sits at Type 2.
• Derivation: applying productions to expand the start symbol into a string — leftmost derivation (expand leftmost non-terminal first) vs rightmost derivation.
• Parse tree: graphical representation of a derivation.
• Ambiguous grammar: a grammar where some string has more than one parse tree / leftmost derivation — undesirable, usually rewritten (e.g., via precedence rules) to remove ambiguity.

Example

Grammar for simple arithmetic expressions:

E → E + E | E * E | ( E ) | id

This grammar is ambiguous (no precedence enforced) — id + id * id has two different parse trees depending on grouping.

📌 CSS Frequency: High — "define CFG, show it's ambiguous, construct a parse tree" is a recurring long question.

Model Answer (short)

"A context-free grammar consists of terminals, non-terminals, production rules, and a start symbol, and is used because it can express recursive/nested constructs that regular expressions cannot. A grammar is ambiguous if some string has two distinct parse trees; compilers typically rewrite such grammars using precedence and associativity rules to remove ambiguity before parsing."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q8(b) · 5 marks

Q. Explain five properties of language using the example of English. Explain why a software language like MiniJava meets these properties as well.

Ans.

• 1. Vocabulary (alphabet and words): English has letters and words. MiniJava has a fixed set of symbols and tokens (keywords, identifiers, operators).
• 2. Syntax (grammar): rules decide which word sequences are valid sentences. MiniJava's syntax is defined by a context-free grammar (BNF).
• 3. Semantics (meaning): valid sentences have meaning. Each valid MiniJava construct has a defined meaning (for example the type rules and what while does).
• 4. Productivity (infinite sentences from finite rules): English can form unlimited sentences by recursion ("the dog that chased the cat that …"). MiniJava allows unlimited programs by nesting statements and expressions.
• 5. Ambiguity and context: English sentences can be ambiguous and need context. A programming language must be unambiguous, so MiniJava's grammar and precedence rules give each program exactly one meaning.

2016 · Paper-I · Q8(d) · 5 marks

Q. What do you mean by a Context-Free Grammar (CFG)? Illustrate with examples.

Ans.

• A CFG is a 4-tuple G = (V, Σ, P, S): V = non-terminals, Σ = terminals, P = production rules of the form A → α (a single non-terminal on the left), S = the start symbol.
• It generates the language of all terminal strings derivable from S. It is more powerful than regular expressions because it can describe nesting (balanced brackets).
• Example 1 (balanced parentheses): S → (S)S | ε
• Example 2 (arithmetic expressions): E → E + T | T, T → T * F | F, F → (E) | id
• Derivation of id + id: E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id.

2018 · Paper-I · Q8(b) · 5 marks

Q. Write a grammar (BNF) for the language of palindromes.

Ans. (Alphabet {a, b}.)

<P> ::= a <P> a | b <P> b | a | b | ε

• The last three rules give the middle of the palindrome (one character for odd length, nothing for even length). Each outer pair of equal characters wraps a smaller palindrome.
• Example: abbba ⇒ a(bbb)a ⇒ a b(b)b a.

2021 · Paper-I · Q8(a)(b) · 4 + 4 marks

Q. For the grammar S → cAd, A → ab | a, construct a top-down parse tree for w = cad, and say whether the grammar is ambiguous.

Ans.

• Top-down parse of cad (with backtracking):
  • start with S and expand S → cAd. Input pointer at c: match c.
  • expand A, trying the first alternative A → ab: match a, then expect b but the input has d, so backtrack
  • try A → a: match a. Then match d. The input is fully consumed, so accepted.

   S
 / | \
c  A  d
   |
   a

• Ambiguity: the grammar is unambiguous. The strings it generates are only cabd and cad, and each has exactly one parse tree, because each string selects exactly one alternative of A.

2021 · Paper-I · Q8(c) · 4 marks

Q. Write the similarities and differences of CFG and regular expression.

Ans.

• Similarities: both define languages formally, both are used in compilers (regular expressions for tokens, CFGs for syntax), and every regular language is also context-free.

2021 · Paper-I · Q8(d) · 4 marks

Q. Design a grammar for "the set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1".

Ans.

• Every string is a sequence of blocks that are either 1 or 01. So:

S → 1S | 01S | ε

• Check: 011 = 01 + 1 ✓, 1101 ✓. The strings 0, 00 and 10 are rejected, because a 0 is never left without a 1 after it. (To require extra 1s after each 0, replace 01 with 011*.)

2022 · Paper-I · Q8(c) · 6 marks

Q. Write a CFG over Σ = {0, 1} for the language of strings of the form 0ᵃ1ᵇ0ᶜ where a + c = b.

Ans.

• Since b = a + c, the string is 0ᵃ 1ᵃ 1ᶜ 0ᶜ: a block 0ᵃ1ᵃ followed by a block 1ᶜ0ᶜ.

S → A B
A → 0 A 1 | ε
B → 1 B 0 | ε

• Check: a = 1, c = 1 gives A = 01 and B = 10, so the string is 0110 (a + c = 2 = b ✓).