Normal Forms for Contextual Grammars
Andrzej Ehrenfeucht, Gheorghe Pǎun, Grzegorz Rozenberg · WORLD SCIENTIFIC eBooks · 1994
Two normal form theorems for contextual grammars with regular choice are given. The first one concerns the (dyna mic) use of productions in derivations when a contextual grammar is executed in the external mode. The second one concerns the (static) relationships between the productions and so it applies to both the external and the internal execution of contextual gram mars. Using the first normal form, a new (more elegant) proof of the linearity of the external languages of contextual grammars with regular choice is given.