Differences between revisions 10 and 12 (spanning 2 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 10 as of 2020-01-26 17:53:10 → 
  Size: 634
  Editor: 68
  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 8:
-. Element  $Σ$  is a finite set, disjoint from [[latex2($V$)]], called the terminals,
+. Element  $Σ$  is a finite set, disjoint from $$V$$, called the terminals,

Diff for "ContexFreeGrammar"