Some Properties of Web Grammars.

摘要

The simplest forms of web grammars are studied with a view toward application to picture pattern recognition. Regular-linear and regular web grammars are defined and proved equivalent to regular string and regular tree grammars respectively. Set down anywhere web automata for these languages are studied. Several properties of context free web grammars are developed. Context free web grammars can be completely reduced. The uvwxy theorem holds for context free web grammars. The two basic normal forms, Chomsky and Greibach,do not exist for context free web grammars. Context sensitive web grammars are equivalent to monotonic web grammars.