Fixpoints in Context-Free Grammars

We show that languages given by context-free grammars are given as least fixpoints of certain continuous functions on languages.

Grammar for expressions such as $x+x*[x+x]*x$ containing variable x, operations +,* and square brackets:

A ::= M | A "+" M
M ::= "x | "x" "*" M | "[" A "]"

Equations on grammars are defined on languages (=sets of words).

This corresponds to the following equations on languages (note how constants correspond to singleton sets, such as $\{x\}$ , $\{+\}$ ):

$\begin{equation*}\begin{array}{l} A = M\ \cup\ A \{+\} M \\ M = \{x\}\ \cup\ \{x\} \{*\} M\ \cup\ \{[\}A\{]\} \end{array} \end{equation*}$

There are multiple solutions of these equations. We are interested in the least solution.

Complete lattice of languages of finite words, and their products.

Context-free grammars are least solutions of recursive equations.

They are in fact given as fixpoints of $\omega$ -continuous functions, as defined in Tarski's fixpoint theorem.

What is the underlying function for context-free grammars?

Why is it $\omega$ -continuous?

General results:

omega continuity of identity and constants
preservation of $\omega$ -continuouty under function composition, projection, pairing

Specific continuous operations: