CONTEXT-FREE LANGUAGES

PAL =

Nonterminals: S
Terminals: 0, 1
Grammar rules/Productions

Def. A CFG is a 4-tuple

V is the set of variables or non-terminals.

is the alphabet of terminal symbols

are finite and disjoint

is the start symbol

P is a finite set of productions of the form

Where and

• Derivation & Languages (Sential Forms)
  • Derivation Trees
• Regular Grammar
• Simplification of CFG
  • Useless Symbols
  • -Productions:
  • Unit Productions
  • Chomsky Normal Form(CNF)
  • Greibach Normal Form(GNF)