3. Examples of Context-Free Grammars

3.1 Grammar for Palindromes over {a, b}

G = ({S}, {a, b}, P, S)
Production Rules:

• S → aSa
• S → bSb
• S → a
• S → b
• S → ε

Generates: Strings like "aba", "abba", "baab", etc., which are palindromes

 

3.2 Grammar for Balanced Parentheses

G = ({S}, {(, )}, P, S)
Production Rules:

• S → (S)
• S → SS
• S → ε

Generates: Strings like "()", "()()", "(())", etc., with balanced parentheses

 

3.3 Grammar for Arithmetic Expressions

*G = ({E, T, F}, {+, , (, ), id}, P, E)
Production Rules:

• E → E + T
• E → T
• T → T * F
• T → F
• F → (E)
• F → id

Generates: Expressions like "id + id * id", "(id + id) * id", etc.

 

4. Key Concepts Related to CFGs

4.1 Derivation

A sequence of production rules applied to the start symbol to obtain a string of terminals

4.2 Parse Tree

A graphical representation of derivation showing the structure of the string based on applied production rules

4.3 Ambiguity

A CFG is ambiguous if at least one string has more than one distinct parse tree. Ambiguity is undesirable in compiler design

4.4 Leftmost and Rightmost Derivations

• Leftmost Derivation: Always replace the leftmost non-terminal first
• Rightmost Derivation: Always replace the rightmost non-terminal first

 

5. Relationship to Pushdown Automata

• CFGs are equivalent to Pushdown Automata (PDA)
• For every CFG, there exists a PDA accepting the same language
• PDAs are used to recognize context-free languages

Note: CFGs are essential in computer science fields like compiler design, programming language theory, and formal verification

 

6. Identifying Context-Free Grammars

A grammar is context-free if all production rules follow the format:

A → α

Where:

• A: Single non-terminal (variable)
• α: Any string of terminals, non-terminals, or ε (empty string)

 

7. Key Characteristics of CFGs

• Left-hand side of each production has exactly one non-terminal
• Right-hand side can be any combination of terminals and non-terminals, or ε
• Application of production rules is independent of the surrounding context

 

8. Checklist to Identify a CFG

• ✅ Only one non-terminal symbol on the left-hand side
• ✅ Any combination of terminals and non-terminals allowed on the right-hand side
• ✅ No dependence on surrounding symbols

 

9. Examples for Better Understanding

9.1 Example 1: CFG

Production Rules:

• S → a S b
• S → ε

Reason: Left-hand side has one non-terminal, right-hand side valid → This is a CFG

 

9.2 Example 2: CFG (Arithmetic Expression Grammar)

Production Rules:

• E → E + T
• E → T
• T → T * F
• T → F
• F → (E)
• F → id

Reason: All rules follow CFG structure → This is a CFG

 

9.3 Example 3: Not a CFG

Production Rule:

• a S b → a a b

Reason: Left-hand side has more than one symbol → This is NOT a CFG (Context-Sensitive)

 

9.4 Example 4: CFG (Also Regular Grammar)

Production Rules:

• A → a A
• A → b

Reason: Left-hand side has a single non-terminal; follows right-linear form → This is both a CFG and Regular Grammar

 

9.5 Example 5: Not a CFG

Production Rule:

• A B → C

Reason: Left-hand side has more than one non-terminal → This is NOT a CFG

 

10. Summary

A grammar is Context-Free if:

• Each production rule is of the form A → α, where:
• A is a single non-terminal
• α is any combination of terminals and non-terminals (including ε)

If the left-hand side has more than one symbol or depends on surrounding context, the grammar is not context-free

 

11. Important MCQs on Context-Free Grammars

11.1 Question 1

Which of the following statements about context-free grammars is FALSE?

(A) Every regular language can be described by a context-free grammar
(B) Context-free grammars can describe some non-regular languages
(C) Context-free grammars can be parsed by finite automata
(D) Context-free grammars are used in compiler design

Answer: (C)

Explanation: CFGs require pushdown automata, not finite automata, for parsing

 

11.2 Question 2

Consider the CFG: S → a S | b S | ε

Which of the following strings CANNOT be generated?

(A) abab
(B) baab
(C) aabb
(D) abc

Answer: (D)

Explanation: The grammar generates only strings of {a, b}*, but "abc" contains c, which is not part of the terminal set

 

11.3 Question 3

Which statement is TRUE regarding ambiguous CFGs?

(A) Every CFG is unambiguous
(B) An ambiguous grammar has more than one parse tree for some strings
(C) Ambiguity simplifies parsing
(D) Ambiguous grammars can always be converted into unambiguous grammars

Answer: (B)

Explanation: Ambiguity means a string can have more than one parse tree

 

11.4 Question 4

Which of the following grammars is context-free?

(A) S → a S b | b S a
(B) a S b → a b
(C) A → B C with condition that A must be followed by a
(D) a A → b

Answer: (A)

Explanation: Only option (A) follows CFG rules with one non-terminal on the left-hand side

 

11.5 Question 5

What is the primary purpose of converting a CFG to Chomsky Normal Form (CNF)?

(A) To make the grammar more ambiguous
(B) To simplify the grammar while preserving the language
(C) To allow the grammar to generate more languages
(D) To make parsing more difficult

Answer: (B)

Explanation: CNF simplifies the grammar, preserving the language, making parsing algorithms more efficient