Differences between revisions 2 and 10 (spanning 8 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 latex2($(V,\Sigma,R,S)$), where

Element $V$ $ is a finite set called the variables,
Element $Σ$ is a finite set, disjoint from latex2($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 10 as of 2020-01-26 17:53:10 → ⇥
  Size: 634
  Editor: 68
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 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 [[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

An example of a rule is 

 $A \to a B a$ 
 $B \to ϵ$

Diff for "ContexFreeGrammar"