Chapter 3 · Watch, then practise
Context Free Grammar
Describe nested structure with grammars and connect derivations to stack-based recognition.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Variables and terminals
- Derivations
- Ambiguity
- Pushdown automata
Chapter playlists
Choose a playlist
Notes
Lec-46: What is Context free grammar in TOC | Formal Definition
Gate Smashers · 7:57
Choose a video · 2 lectures
Pairs the chapter’s CFG definition with a supplementary language-to-grammar construction lesson.
1. Building a grammar
Give a grammar for {aⁿbⁿ | n ≥ 0} and derive aaabbb.
Use start variable S and rules S → aSb | ε. A derivation is S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb. Each recursive step adds one a before and one b after the remaining variable. Ending with ε ensures equal counts; zero recursive steps generate the empty string.
Lec-37: Ambiguous vs Unambiguous Grammar with examples | Conversion Ambiguous ➡️ Unambiguous
Gate Smashers · 9:30
Supplementary grammar-ambiguity lesson for alternative parses of an expression.
2. Ambiguous expressions
Why is E → E + E | E × E | x ambiguous?
The string x + x × x can have a parse grouping the addition first or grouping the multiplication first. One string with two distinct parse trees suffices for ambiguity. Separate expression, term and factor variables can encode multiplication precedence and remove this particular ambiguity.
Lec-55: What is Pushdown Automata in TOC | Definition & Explanation in Hindi
Gate Smashers · 10:58
Choose a video · 2 lectures
Introduces PDA operation, then a related counting example with a different ratio from the language in this question.
3. Recognizing with a stack
How can a PDA recognize aⁿbⁿ, and which malformed inputs must it reject?
Push a marker for each a, then pop one for each b. Once the b phase starts, reject another a. Reject if a b has no marker, or if markers remain at end of input. Accept ε separately and accept other inputs only when all input is consumed with matched counts.