Differences between revisions 6 and 11 (spanning 5 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 , where

Element $ is a finite set called the variables,
Element is a finite set, disjoint from latex2($V$), called the terminals,
Element is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
Element is the start variable

An example of a rule is

-  ⇤ ← Revision 6 as of 2005-09-01 00:34:40 → 
  Size: 689
  Editor: yakko
  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:
-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:
-. Element [[latex2($V$)]] is a finite set called the variables,
 1. Element [[latex2($\Sigma$)]] is a finite set, disjoint from [[latex2($V$)]], called the terminals,
 1. Element [[latex2($R$)]] is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
 1. Element [[latex2($S \in V$)]] is the start variable
+. Element $$V$$$ is a finite set called the variables,
 1. Element $$\Sigma$$ 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
 Line 14:
-{{{
latex2($A \rarrow aBa$)
latex2($B \rarrow \epsilon$)

}}}
+$$A \rightarrow aBa$$
$$B \rightarrow \epsilon$$

Diff for "ContexFreeGrammar"