𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A chomsky hierarchy of isotonic array grammars and languages

✍ Scribed by Curtis R. Cook; Patrick Shen-Pei Wang

Publisher
Elsevier Science
Year
1978
Weight
484 KB
Volume
8
Category
Article
ISSN
0146-664X

No coin nor oath required. For personal study only.

✦ Synopsis

An array is a two-dimensional generalization of a string. Both sides of each rewriting rule of an isotonic array grammar have the same shape. In this paper we complete the Chomsky hierarchy of isotonic array grammars by introducing isotonic context-free array grammars. We obtain Chomsky and Greibach normal forms for context-free array grammars. We show that the one-dimensional (vertical or horizontal) isotonic regular and context-free array languages coincide and are closely related to the regular string languages. We also obtain a finite s~ate recognizer characterization of regular array languages.

πŸ“œ SIMILAR VOLUMES

Algorithms for producing grammars from s
Algorithms for producing grammars from sample derivations: a common problem of formal language theory and developmental biology
✍ Horacio Feliciangeli; Gabor T. Herman πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 926 KB

We give a number of algorithms which for a finite set of finite sequences of strings of symbols decide whether or not there exists a grammar of a certain fixed type such that each of the sequences is a derivation (or subderivation) by the grammar. Whenever such grammars exist, our algorithms will ef