Old and new Transformations of Grammars: Structural, Algorithmic and Linguistic Applications

Eli Shamir

Abstract

Formal grammars provide a rich combinatorial theory and useful applications. We consider primarily the context–free [CF] model, its sub-models and "mild" extensions as well. The known transformations, simple and subtle, between various forms of the grammars encompass much of the theory and the applications: parsing schemes in compiler's technology, homomorphisms theorems, hardest context-free languages and more.

Our novel scheme utilizes heavily the manner CFG derives its trees and terminal strings, graded by the derivation semi-order on the symbols. Essentially, alternate pairs of spread and rotate operations, which will be defined, enable transition from product of factors to union of components.

They create an operation-tree which transforms the original grammar at the root into a bunch of elongated thin threads at the leaves of the tree-namely