scientific article; zbMATH DE number 4108176
An apical growth filamentous system (briefly AGFS) is a triple \(G=(V,P,w)\), where V is a finite alphabet, \(w\in V^+\) is the axiom and \(P=P_{left}\cup P_{right}\) is a set of context-free rewriting rules over v. The elements of \(P_{left}\) are called left rules and those of \(P_{right}\) are called right rules. In this paper the author proves the equivalence of regular controlled AFGS (extended or not, with finite set of axioms or not) with linear grammars. An extended AGFS (briefly EAGFS) is a system \(G=(V,T,P,w)\) where \(T\subseteq V\) and the language generated consists of strings \(x\in T^*\) such that \(w\Rightarrow^{*}x\) in the AGFS(V,P,w); an AGFS with a finite number of axioms (briefly FAGFS) is an AGFS with a set W of axioms and the generated language consists of all strings \(x\in V^*\) such that \(x\Rightarrow^{*}w\) for some \(w\in W\). The main result is the following Theorem: \((R)AGFL=(R)FAGFL=(R)EAGFL=LIN\). Here are denoted by (R)AGFL, (R)FAGFL, (R)EAGFL and LIN the regular controlled families of languages corresponding respective to AGFL, EAGFL, FAGFL and linear languages (AGFL is the family of languages correspondin to AGFS, a.s.o.). By this paper the author emphasizes new possibilities to characterize the so important family of linear languages.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3832068)