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?
- 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)