โ† Theory of Computation learning path
Theory of Computation ยท Module 6 of 10

Context-free grammars

Grammars, derivations and parse trees.

๐Ÿ“– Key ideas

  1. A CFG has variables, terminals, productions (A -> string) and a start symbol.
  2. Derivations replace variables using productions; leftmost and rightmost derivations differ in order.
  3. A parse tree shows the structure of a derivation.
  4. A grammar is ambiguous if some string has two parse trees.
  5. 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