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
- Element
$ is a finite set called the variables, - Element
is a finite set, disjoint from , called the terminals, - Element
is a finite set of rules, with each rule being a variable and a string of variables and terminals, and - Element
is the start variable
An example of a rule is