Differences between revisions 2 and 12 (spanning 10 versions)

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, Σ, R, S)$ , where

Element $V$ $ is a finite set called the variables,
Element $Σ$ 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 \to a B a$ $B \to ϵ$

-  ⇤ ← Revision 2 as of 2005-09-01 00:00:49 → 
  Size: 478
  Editor: yakko
  Comment:
+   ← Revision 12 as of 2020-01-26 17:53:59 → ⇥
  Size: 614
  Editor: 68
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 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:
-.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
+. Element $$V$$$ is a finite set called the variables,
 1. Element  $Σ$  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 \to a B a$ 
 $B \to ϵ$

Diff for "ContexFreeGrammar"