Context equivalence and context-free normal forms

A set of transformations is presented that will convert an arbitrary context-free grammar to extended versions of the eight normal forms that have exactly two nonterminals on the right hand side of their longest productions. Six of these transformations form the basis of a meta-normal form algorithm for context-free grammars, which takes as input an arbitrary context-free grammar and a target normal form, expressed as a two-symbol grammar form, and converts the grammar to that normal form. The number of nonterminals in the output grammars of each of the six base transformations is minimal.; A new type of automaton for linear languages, the finite state shuffle automaton1, is defined and a normal form is given. Linear context languages (Lˆ) and a context equivalence relation (∼) for them are introduced. Linear context equivalence class membership is shown to be undecidable. Deterministic finite state shuffle automata accept a proper subset of the linear languages that properly includes the regular languages. It is shown that the languages accepted by these automata are recognizable and that the index of ∼ for these languages is finite. An upper bound on the number of states of the factor automaton mod ∼ for a deterministic finite state shuffle automaton in normal form that accepts a regular language is estimated. As a consequence, an upper bound can be computed for the number of nonterminals in the output grammars of the two of the eight presented normal form transformations which are not part of the basis of the meta-normal form algorithm for context-free grammars. These transformations are those in which the right hand side of each production both begins and ends with a terminal symbol.; 1After completion of this work I discovered that the term shuffle automaton has been previously applied to automata used for recognizing behaviour patterns in distributed systems [3] and again in the past year to automata that accept shuffle languages [23]. The mathematics structures described by these terms are, however, unrelated and quite different.