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.V is a finite set called the variables,
- is a finite set, disjoint from V, called the terminals, 3.R is a finite set of rules, with each rule being a variable and a string of variables and terminals, and 4.S∈V is the start variable