|
Size: 689
Comment:
|
Size: 693
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 14: | Line 14: |
| {{{ latex2($A \rarrow aBa$) latex2($B \rarrow \epsilon$) }}} |
[[latex2($A \rightarrow aBa$)]] [[latex2($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 latex2($(V,\Sigma,R,S)$), where
Element latex2($V$) is a finite set called the variables,
Element latex2($\Sigma$) is a finite set, disjoint from latex2($V$), called the terminals,
Element latex2($R$) is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
Element latex2($S \in V$) is the start variable
An example of a rule is
latex2($A \rightarrow aBa$) latex2($B \rightarrow \epsilon$)