context-free grammar (thing)

Context Free Grammars:
A Context Free Grammar is a 4-tuple.
( V , SIGMA , R , S )
V = Set of Variables or Symbols
SIGMA = The Alphabet (terminals)
R = Set of Rules
S = Start Rule

A Rule is of the form:
Symbol -> String
Where 'Symbol' is a member of V and 'String' is a string over the set V U SIGMA. An example rule would be:
S -> aBa
This can be read as 'S may be replaced with aBa'
By convention Symbols are capitalized and terminals are not.
It is possible to have two rules that share a Symbol on the left. For instance, consider the two rules:
S->bSb
S->aBa
In a case such as this, S can be replaced with either one of {bSb,aBa}
There is a shorthand for this.
S->bSb | aBa

If a Language L is a Context Free Language iff there is some Context Free Grammar, G, that for every string w in L, there is a derivation of w in G. A derivation is a sequence of substitutions (as permitted by the set of rules) to obtain a string.

Example(pg.92):
A CFG Gis defined by:

V = {A,B}
SIGMA = {0,1,#}
R = {
      A -> 0A1 ,
      A -> B ,
      B -> #
     }
S = A

0#1 is a string in the Language of G
This is because, starting with A, there is a sequence of substitutions that will end with the string 0#1
A derivation is of 0#1 is described as follows:

• Start with A
• Look in the set of rules,
  Find an A on the left-hand side of a rule. There are two possible substitutions
• We will replace A with the right-hand side of one of the rule s.
  Our A is now 0A1
• It is time for another replacement. 0 and 1 are terminals. They are nonreplacable. Remember SIGMA and V are disjoint set s.
  The only thing to replace is the A.
• This time we replace A with B by the second rule from our set.
  This leaves us with the string 0B1.
• B is the only symbol (or variable) and there is only one rule for replacing B.
  This leaves us with the string 0#1

We can write the above sequence of substitiutions as a flat derivation, in the following way:

A => 0A1 => 0B1 => 0#1

This derivation is read as:
A yeilds 0A1, which yeilds 0B1, which yeilds 0#1

A flat derivation for the string 000#111 is explained on page 92 of Michael Sipsers An Introduction to the Theory of Computation and is written as follows:

A => 0A1 => 00A11 => 000A111 => 000B111 => 000#111