Relating Chomsky Normal Form and Greibach Normal Form by exponential transposition: towards the categorification of the theory of context-free languages

Jürgen Koslowski

Abstract

We show that the Chomsky Normal Form and the Greibach Normal Form of context-free grammars are related via exponential transposition, or Currying. This results from combining Bob Walters' approach to context-free grammars with an observation concerning the equivalence of certain kinds of trees as inductive data types. On the one hand, this leads to a new more conceptual algorithm for constructing Greibach normal forms. But it also suggests a natural extension of Walters' approach that subsumes the familiar dichotomy between finite state automata and regular grammars, a feature missing from Walters' original set-up. Further techniques from the categorical treatment of labeled transition systems then become available, e.g., the notions of simulation and bisimulation arise naturally for context-free grammars as well as for push-down automata. Our methods readily extend to variations of context-free languages, e.g., weighted ones.