Differences between revisions 10 and 11
⇤ ← Revision 10 as of 2020-01-26 17:53:10 →
Size: 634
Editor: scot
Comment:
← Revision 11 as of 2020-01-26 17:53:27 → ⇥
Size: 624
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

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 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)