โ Theory of Computation learning pathTheory of Computation ยท Module 6 of 10
Context-free grammars
Grammars, derivations and parse trees.
๐ Key ideas
- A CFG has variables, terminals, productions (A -> string) and a start symbol.
- Derivations replace variables using productions; leftmost and rightmost derivations differ in order.
- A parse tree shows the structure of a derivation.
- A grammar is ambiguous if some string has two parse trees.
- Normal forms: Chomsky Normal Form (A -> BC or A -> a) and Greibach Normal Form.
๐ก Real-life example: A grammar is like the rules of a sentence: Sentence -> Subject Verb Object, and each part breaks down further into words.
Context-free grammarGrammar with a single variable on the left of each rule
Parse treeTree showing how a string is derived
Ambiguous grammarGrammar giving some string two parse trees
Chomsky Normal FormRules of form A -> BC or A -> a