CFGs.txt

Take a simple expression grammar G:

  E = n | (E + E)

A language is a set of strings. The grammar corresponds to an operator mapping languages to languages:

  G(X) = {n} union {(e1 + e2) | e1 in X, e2 in X}

G's language L is the least fixed point of this operator, which is essentially the limit of G(X) starting with X = {}:

    L_0 = {}
    L_n = G(L_(n-1))

Then G's language L equals lim(n->infinity) L_n. We can get a feel for this by computing a bunch of finite approximations:

    L_0 = {}
    L_1 = G({}) = {n} union {(e1 + e2) | e1 in {}, e2 in {}}
        = {n}
    L_2 = G({n})
        = {n} union {(e1 + e2) | e1 in {n}, e2 in {n}}
        = {n, (n + n)}
    L_3 = G({n, n + n}})
        = {n} union {(e1 + e2) | e1 in {n, (n + n)}, e2 in {n, (n + n)}}
        = {n} union {(n + n), (n + (n + n)), ((n + n) + n), ((n + n) + (n + n))}
        = {n, (n + n), (n + (n + n)), ((n + n) + n), ((n + n) + (n + n))}
        
You can see how it builds up from level to level and how each finite approximation contains its predecessor.

Note how there's no special treatment of left recursion.