Effective constructions of grammars. (English) Zbl 0782.68073

Novotný, Miroslav

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.).

Reviewer: G.Paun (Bucureşti)

MSC:

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

Keywords:

strictly monotone pure grammars

Citations:

Zbl 0745.00057