NTS languages are deterministic and congruential

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove here that such grammars generate deterministic languages which are finite unions of congruence classes. Moreover, we show that this family of languages is closed under reversal and intersection with regular sets. A forthcoming paper will prove that, for this class, the equivalence problem is decidable.     

Simple restriction in context-free rewriting

Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with λ-productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or − to each nonterminal. A production is applicable if it is applicable as a context-free production and if the symbol assigned to the left-hand side of the production is coupled with +, then this symbol has to appear in the sentential form, while if coupled with −, it must not appear in the sentential form. This restriction is simpler than most of the other restrictions, since the context conditions are assigned to nonterminals, not to productions, and their type is the simplest possible – a nonterminal.     

Forbidding and enforcing in membrane computing

Motivated by biochemistry and the non-deterministic reactions between molecules,the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems(fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second casethe membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders.     

Characterizations of regular and context-free matrices

The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.     

An infinite hierarchy of intersections of context-free languages

The class of languages expressible as the intersection ofk context-free languages is shown to be properly contained within the class of languages expressible as the intersection ofk + 1 context-free languages. Hence an infinite hierarchy of classes of languages is exhibited between the class of context-sensitive languages and the class of context-free languages.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

On the number of components in cooperating distributed grammar systems

It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components.     

Pattern selector grammars and several parsing algorithms in the context-free style

Pattern selector grammars are defined in general. We concentrate on the study of special grammars, the pattern selectors of which contain precisely κ “one”s (01(101)^κ) or κ adjacent “one”s (011^κ01). This means that precisely κ symbols (resp. κ adjacent symbols) in each sentential form are rewritten. The main results concern parsing algorithms and the complexity of the membership problem. We first obtain a polynomial bound on the shortest derivation and hence an NP time bound for parsing. In the case κ = 2, we generalize the well-known context-free dynamic programming type algorithms, which run in polynomial time. It is shown that the generated languages, for κ = 2, are log-space reducible to the context-free languages. The membership problem is thus solvable in log² space.     

Formes de langages et de grammaires

Summary This paper is devoted to the study of context-free languages over infinite alphabets. This work can be viewed as a new attempt to study families of grammars, replacing the usual grammar forms and giving a new point of view on these questions. A language over an infinite alphabet or I-language appears as being a model for a family of usual languages; an interpretation is an homomorphism from the infinite alphabet to any finite alphabet. Using this notion of interpretation we can associate to each family of I-languages an image, called its shadow, which is a family of usual languages.The closure properties of families, generalizing to infinite alphabets the family of context-free languages, lead to define rational transductions between infinite alphabets or I-transductions, and then, families of I-languages closed under I-transductions, or I-cones. We study here relations between the closure properties of a family of I-languages and these of its shadow. As a result, we obtain that any union closed rational cone of context-free languages, principal or not, is the shadow of a principal I-cone.This work leads to new results about the classical theory of context-free languages. For instance, we prove that any principal rational cone of context-free languages can be generated by a context-free language, whose grammar has only 6 variables. This work also leads to more general considerations about the adequacy of some generating devices to the generated languages. It appears that the context-free grammars are fair, in a sense that we define, for generating context-free languages but that non-expansive context-free grammars are not for generating non-expansive context-free languages. This point of view raises a number of questions.     

A pumping lemma for random permitting context languages

Random context grammars belong to the class of context-free grammars with regulated rewriting. Their productions depend on context that may be randomly distributed in a sentential form. Context is classified as either permitting or forbidding, where permitting context enables the application of a production and forbidding context inhibits it. For random context languages of finite index a generalization of the well-known pumping lemma for context-free languages has been proven. We drop the finite index restriction and concentrate on non-erasing grammars that use permitting context only. We prove a pumping lemma for their languages that generalizes and refines the existing one, and show that these grammars are strictly weaker than the non-erasing random context grammars.     

Investigations on Hotz groups for arbitrary grammars

Summary The Hotz group H(G) and the Hotz monoid M(G) of an arbitrary grammar G=(V, X, P, S) are defined by H(G)=F(VX)/P and M(G) =(VX)^*/P respectively. A language LX^* is called a language with Hotz isomorphism if there exists a grammar G with L=L(G) such that the natural homomorphism F(X)/LH(G) is an isomorphism. The main result of this paper states that homomorphic images of sentential form languages are languages with Hotz isomorphism. This is a generalization of a result of Frougny, Sakarovitch, and Valkema on context-free languages.Hotz groups are used to obtain lower bounds for the number of productions which are needed to generate a language. Further it is shown that there are languages with Hotz isomorphism without being a homomorphic image of a sentential form language, and there are context-sensitive languages without Hotz isomorphism. The theory of Hotz monoids is used to get some results on languages generated by grammars with a symmetric set of rules.     

The equivalence and inclusion problems for NTS languages

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove that this class of grammars has a decidable equivalence problem. Then we show that one can decide whether a given c.f. grammar is NTS or not. We prove that the class of NTS grammars has an undecidable inclusion problem.     

One-sided forbidding grammars and selective substitution grammars

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a non-terminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form, while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, this paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, this paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.     

Highly Constrained Unification Grammars

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.     

Le cylindre des langages linéaires

Define a cylinder to be a family of languages which is closed under inverse homomorphisms and intersection with regular sets. A number of well-known families of languages are cylinders:

—CFL, the family of context-free languages, is a principal cylinder, i.e. the smallest cylinder containing a languageL _O described in [6].

—the family of deterministic context-free languages is proved to be a nonprincipal cylinder in [7].

—the family of unambiguous context-free languages is a cylinder: to prove that it is not principal seems to be a very hard problem.

In this paper we prove that Lin, the family of linear context-free languages, is a nonprincipal cylinder. This is achieved in the standard way by exhibiting a sequence of languages S_n, n∈N, such that Lin is the union of all the principal cylinders generated by these languages and is not the union of any finite number of these cylinders. This leaves open the problem raised by Sheila Greibach of whether there exists a languageL such that every linear context-free language is the image ofL in some inverse gsm mapping.     

An NC algorithm for recognizing tree adjoining languages

A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system which has applications in natural language processing. This class of languages is known to properly include all context-free languages; for example, the noncontext-free sets {a ⁿ b ⁿ c ⁿ } and {ww} are in this class. It is shown that the recognition problem for tree adjoining languages can be solved by a concurrent read, concurrent write parallel random-access machine (CRCW PRAM) inO(logn) time using polynomially many processors. Thus, the class of tree adjoining languages is inAC ¹ and hence inNC. This extends a previous result for context-free languages.This research was supported in part by NSF Grants IRI 92-96249, MCS 82-19116-CER, MCS 82-07294, DCR 84-10413, MCS 83-05221, ARO Grant DAA29-84-9-0027, DARPA Grant N00014-85-K-0018, and by the New Jersey Institute of Technology under Grant Nos. 421690 and 211665.     

On restricted context-free grammars

Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols.     

On grammar forms with terminal context

Summary A context-free grammar form G defines a family of context-free grammars {ie397-01}(G). In this paper {ie397-02}(G) is extended to give the family of terminal context grammars {ie397-03}(G), which were introduced by Book [4]. It is shown that the families of languages defined by {ie397-04}(G) and {ie397-05}(G) are equal when G is an -free context-free grammar form. This generalizes the result of Book [4] for context-free grammars and underlines the usefulness of the notion of grammar forms in formal language theory.The work of the second author was carried out partially under a National Research Council of Canada Grant. No. A-7700 and partially under the auspices of the University of Karlsruhe     

Left-forbidding cooperating distributed grammar systems

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.