Context Free Grammar

Def: For every ContextFreeLanguage there is a ContextFreeGrammar that generates it and a PushDownAutomata that recognizes it.

A context-free grammar is a 4-tuple latex2($(V,\Sigma,R,S)$), where

  1. Element $ is a finite set called the variables,

  2. Element is a finite set, disjoint from latex2($V$), called the terminals,

  3. Element is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
  4. Element is the start variable

An example of a rule is