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 $(V,\mathrm{\Sigma },R,S)$, where

1. Element $V$$ is a finite set called the variables,
2. Element $\mathrm{\Sigma }$ is a finite set, disjoint from $V$, called the terminals,
3. Element $R$ is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
4. Element $S\in V$ is the start variable

An example of a rule is

$A\to aBa$ $B\to ϵ$