Differences between revisions 10 and 12 (spanning 2 versions)
⇤ ← Revision 10 as of 2020-01-26 17:53:10 →
Size: 634
Editor: scot
Comment:
← Revision 12 as of 2020-01-26 17:53:59 → ⇥
Size: 614
Editor: scot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: 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: Line 8:
 1. Element is a finite set, disjoint from [[latex2($V$)]], called the terminals,  1. Element is a finite set, disjoint from $$V$$, called the terminals,

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 , where

  1. Element $ is a finite set called the variables,
  2. Element is a finite set, disjoint from , 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)