|
Size: 560
Comment:
|
← Revision 12 as of 2020-01-26 17:53:59 ⇥
Size: 614
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| A context-free grammar is a 4-tuple [[latex2($(V,\Sigma,R,S)$)]], where | A context-free grammar is a 4-tuple $$(V,\Sigma,R,S)$$, where |
| Line 7: | Line 7: |
| 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 |
1. Element $$V$$$ is a finite set called the variables, 1. Element $$\Sigma$$ is a finite set, disjoint from $$V$$, called the terminals, 1. Element $$R$$ is a finite set of rules, with each rule being a variable and a string of variables and terminals, and 1. Element $$S \in V$$ is the start variable An example of a rule is $$A \rightarrow aBa$$ $$B \rightarrow \epsilon$$ |
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,\Sigma,R,S)$$, where
- Element $$V$$$ is a finite set called the variables,
- Element $$\Sigma$$ is a finite set, disjoint from $$V$$, called the terminals,
- Element $$R$$ is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
- Element $$S \in V$$ is the start variable
An example of a rule is
$$A \rightarrow aBa$$ $$B \rightarrow \epsilon$$