scientific article; zbMATH DE number 3990895
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\) ?
- scientific article; zbMATH DE number 3872708
- scientific article; zbMATH DE number 4074515
- A variant of random context grammars: Semi-conditional grammars
- Semilinearity of families of languages
- Semilinearity of families of languages
- scientific article; zbMATH DE number 4160148
- On the power of permitting semi-conditional grammars
- On internal contextual grammars with maximal use of selectors
- Descriptional complexity of semi-conditional grammars
- Characterizations of recursively enumerable languages by means of insertion grammars
- On languages in countably generated semilattices
- On the expressive power of GF(2)-grammars
- Regulated RNA rewriting: Modelling RNA editing with guided insertion
- Two results on discontinuous input processing
- scientific article; zbMATH DE number 4160148 (Why is no real title available?)
- scientific article; zbMATH DE number 3986657 (Why is no real title available?)
- scientific article; zbMATH DE number 4074515 (Why is no real title available?)
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)