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\}$, $\{+\}$):

  A = M\ \cup\ A \{+\} M \\
  M = \{x\}\ \cup\ \{x\} \{*\} M\ \cup\ \{[\}A\{]\}

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:

  • union of languages
  • concatenation (proof has one interesting step when comparing infinite unions)