A general grammar is a 4-tuple (Sigma,V,S,P) where

Sigma is an alphabet, whose members are called terminals.

V is an alphabet, whose memebers are called variables.

V and Sigma are disjoint.  The union Sigma+V is called the alphabet of
grammar symbols.

S in V is called the start symbol.

P is a finite set of productions.  Each production is an ordered pair
(x,y) where x and y are both strings of grammar symbols, and at least
one of the symbols of x is a variable.  We call x the left-hand-side
and y the right-hand-side of (x,y) in P.

We usually write x->y instead of (x,y).

Given a general grammar G = (Sigma,V,S,P), we define a relation =>,
which we call "derives in one step by G" as follows.  If x->y in P
and if u and v are arbitrary strings of grammar symbols, then uxv => uyv.

We define a relation =>*, which we call "derives by G" to be the
transitive reflexive closure of =>.  Recursively, we define =>* by:

Basis: If x is any string of grammar symbols, then x =>* x.
Recurrence: If x, y, and z are any strings of grammar symbols,
	and if x =>* y and y => z, then x =>* z.
Extension: In no other cases is it true that x =>* y.

Define L(G) to be the set of all strings w over Sigma such that S =>* w.
We say L(G) is the language generated by G.

  ------------------------------------------------------------------

Question: is every language generated by a general grammar?  Answer: No,
but it isn't easy to think of one that isn't.

Let L be the set of all strings over {1} whose length is a power of 2.
That is, L = {1, 11, 1111, 11111111, ... }
Here is a general grammar that generates L.

V =  {S,A,B,D}

P consists of the following productions:

	S -> A1B
	A -> AD
	A -> emptystring
	D1 -> 11D
	DB -> B
	B -> emptystring

Here is a derivation of the string 1111:

S => A1B =>
AD1B => A11DB => A11B =>
AD11B => A11D1B => A1111DB => A1111B =>
1111B => 1111