Size: 295
Comment:
|
Size: 624
Comment:
|
Deletions are marked like this. | Additions are marked like this. |
Line 5: | Line 5: |
A context free grammar consists of a set of rewritting rules or productions of the form | A context-free grammar is a 4-tuple |
Line 7: | Line 7: |
1. Element 1. Element 1. Element 1. Element |
|
Line 8: | Line 12: |
An example of a rule is | |
Line 9: | Line 14: |
{{{ symbol --> symbol symbol... }}} |
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 latex2($V$), 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