Differences between revisions 7 and 10 (spanning 3 versions)
⇤ ← Revision 7 as of 2005-09-01 00:34:52 →
Size: 683
Editor: yakko
Comment:
← Revision 10 as of 2020-01-26 17:53:10 → ⇥
Size: 634
Editor: scot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 7: Line 7:
 1. Element [[latex2($V$)]] is a finite set called the variables,
 1. Element [[latex2($\Sigma$)]] is a finite set, disjoint from [[latex2($V$)]], called the terminals,
 1. Element [[latex2($R$)]] is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
 1. Element [[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 [[latex2($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
Line 14: Line 14:
{{latex2($A \rarrow aBa$)
latex2($B \rarrow \epsilon$)
}}		 $$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 latex2($(V,\Sigma,R,S)$), where

  1. Element $ is a finite set called the variables,

  2. Element is a finite set, disjoint from latex2($V$), called the terminals,

  3. Element is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
  4. Element is the start variable

An example of a rule is

ContexFreeGrammar (last edited 2020-01-26 17:53:59 by scot)