Context-Free Grammars

Rules, Derivations & Parse Trees

1:00

How context-free grammars use recursive production rules, derivations, and parse trees to describe nested structure that regular expressions cannot.

By the end, you can

Name the four components of a grammar G = (V, Σ, R, S) and explain what each one is.
Distinguish terminals from nonterminals and identify the head and body of a production rule.
Trace a derivation step by step and explain when it terminates.
Draw or read a parse tree and identify its yield.
Explain why a DFA cannot recognize a^n b^n and why a CFG can.
Define ambiguity and describe how stratifying nonterminals by precedence resolves it.
Describe what a pushdown automaton is and how it recognizes a^n b^n using a stack.
Place CFGs in the Chomsky hierarchy and name the machine for each level.
State why a^n b^n c^n lies outside the context-free languages.
Give at least three practical domains where CFGs are used.

Up next in Theory of Computation & Compilers