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. latex2($V$) is a finite set called the variables,

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

  3. latex2($R$) is a finite set of rules, with each rule being a variable and a string of variables and terminals, and

  4. latex2($S \in V$) is the start variable