scientific article; zbMATH DE number 3990895

From MaRDI portal
Publication:3753509





In this paper the author considers a semicontextual grammar as a triple \(G=(V,B,P)\), where V is a nonempty finite alphabet, B is a finite language over V, and P is a finite set of rewriting rules of the form xy\(\to xzy\), x, y, z being non-null strings over V. Then, if \(\Rightarrow^{*}\) denotes the reflexive transitive closure of the relation \(\Rightarrow\), the language generated by G is defined as \(L(G)=\{x\in V^*|\) \(z\Rightarrow^{*}x\) for some z in \(B\}\). A semicontextual grammar G is said to be of degree m if \(m=\max \{| x| |\) xy\(\to xzy\) or yx\(\to yzx\) is a rule in \(P\}\) (\(| x|\) is the length of the string x). Then, the author denotes by \({\mathcal S}_ i\), \(i\geq 1\), the family of languages generated by semicontextual grammar of degree not greater than i. Firstly, the author solves an open problem formulated by B. S. Galyukshov (in 1981) proving the following result (Theorem 1): The family \({\mathcal S}_ 2\) contains non-context-free languages. Then, he gives a result concerning the closure properties of semicontextual language families (Theorem 2): Each family \({\mathcal S}_ i\), \(i\geq 1\), is an anti-AFL). Finally, involving his paper On semicontextual grammars [Bull. Math. Soc. Sci. Math. Repub. Soc. Roum., Nouv. Sér. 28(76), 63-68 (1984; Zbl 0547.68073)], the author formulates an open problem: Is each regular language contained in \(\cup^{\infty}_{i=1}{\mathcal S}_ i\) ?











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