|
Size: 478
Comment:
|
Size: 560
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| 1.V is a finite set called the variables, 2. 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 |
1. [[latex2($V$)]] is a finite set called the variables, 1. [[latex2($\Sigma$)]] is a finite set, disjoint from [[latex2($V$)]], called the terminals, 1. [[latex2($R$)]] is a finite set of rules, with each rule being a variable and a string of variables and terminals, and 1. [[latex2($S \in V$)]] is the start variable |
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
latex2($V$) is a finite set called the variables,
latex2($\Sigma$) is a finite set, disjoint from latex2($V$), called the terminals,
latex2($R$) is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
latex2($S \in V$) is the start variable