# 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 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 , ):

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 -continuous functions, as defined in Tarski's fixpoint theorem.

What is the underlying function for context-free grammars?

Why is it -continuous?

General results:

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

Specific continuous operations:

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