## Effective constructions of grammars.(English)Zbl 0782.68073

Mathematical problems in computation theory, Proc. 26th semester, Warsaw/ Poland 1985, Banach Cent. Publ. 21, 315-328 (1988).
[For the entire collection see Zbl 0745.00057.]
Denote the $$SM$$ the family of languages generated by strictly monotone pure grammars (triples $$(V,P,S)$$ with $$V$$ an alphabet, $$S \in V$$, $$P \subseteq V^* \times V^*$$ and for $$(x,y) \in P$$, $$1 \leq | x |< | y |)$$. Using ideas from analytic linguistics, an algorithm is proposed for inferring grammars starting from samples of languages: given the set $$L_ k$$ of strings of length at most $$k$$, $$k \geq 1$$, in some language $$L$$, the algorithm produces a pure grammar $$G_ k$$ such that $$L_ k \subseteq L(G_ k)$$. It is proved that a language $$L$$ is in family $$SM$$ if and only if this algorithm converges in the sense that there is $$k_ 0$$ such that $$L(G_ k)=L(G_{k_ 0})=L$$, $$k \geq k_ 0$$.
The family $$SM$$ is shown to include strictly the family of regular languages and to be incomparable with the family of context-free language. Two complexity measures for the above algorithm are considered (the smallest $$k_ 0$$ as above and the longest interval of integers smaller than $$k_ 0$$ for which the algorithm produces the same grammar); the last section discusses applications (in artificial intelligence, syntactic pattern recognition, developmental biology etc.).

### MSC:

 68Q42 Grammars and rewriting systems 68Q45 Formal languages and automata

### Keywords:

strictly monotone pure grammars

Zbl 0745.00057