Syntactic complexity of scattered context grammars

The syntactic complexity of scattered context grammars with respect to the number of nonterminals is investigated. First, the family of the recursively enumerable languages is characterized by some basic operations, such as quotient and coding, over the languages generated by propagating scattered context grammars with four nonterminals. Then, a new method of achieving the characterization of the family of recursively enumerable languages by scattered context grammars is given; in fact, this family is characterized by scattered context grammars with only five nonterminals and a single erasing production. Finally, it is demonstrated that the number of nonterminals can be decreased by one in the present characterizations if scattered context grammars start their derivations from a word rather than a single symbol.     

Workspace theorems for regular-controlled grammars

This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled grammar H, there is a positive integer k such that H generates every sentence y∈L(H) by a derivation in which every sentential form x contains at most (k−1)|x|/k occurrences of nonterminals that are erased throughout the rest of the derivation, where |x| denotes the length of x, then the language of H is generated by a propagating regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.     

Nonterminal complexity of one-sided random context grammars

In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.     

Equivalence and reduction of expansive tree grammars

The equivalence of nonterminals of an expansive tree grammar is considered. Algorithms are presented for constructing sets of equivalent nonterminals for an expansive tree grammar, for reducing the grammar, and for determining whether two grammars generate the same language.     

A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars

We present here an equivalence checking algorithm which operates directly on a pair of strict deterministic vs. LL(k) grammars. It is also straightforwardly applicable to a pair of LL(k) grammars, though an LL(k) grammar is not necessarily strict deterministic. The basic idea is from Korenjak and Hopcroft's branching algorithm for simple deterministic grammars, but ours is so distinguished that it is throughout free from mixing the nonterminals of the respective grammars in question and then very simple.     

Scattered context grammars that erase nonterminals in a generalized k-limited way

A scattered context grammar erases nonterminals in a generalized k-limited way in a successful derivation, where k is a positive integer, if in every sentential form of a derivation, each of its substrings consisting of nonterminals from which the grammar derives empty strings is of length k or less. This paper demonstrates that if a scattered context grammar generates its sentences in this way, it can be converted to a scattered context grammar without erasing productions; in general, however, this is not possible.     

Morphismes et bimorphismes d'arbres

For every pair of positive integers n and p, there is a language accepted by a real-time deterministic pushdown automaton with n states and p stack symbols and size O(np), for which every context-free grammar needs at least n²p+1 nonterminals if n>1 (or p non-terminals if n = 1). It follows that there are context-free languages which can be recognized by pushdown automata of size O(np), but which cannot be generated by context-free grammars of size smaller than O(n²p); and that the standard construction for converting a pushdown automaton to a context-free grammar is optimal in the sense that it infinitely often produces grammars with the fewest number of nonterminals possible.     

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.     

A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions

 In this paper, we consider derivation trees in apex NLC graph languages. We show that for every graph H in arbitrary apex NLC graph language, a decomposition tree of H can be constructed from a derivation tree of H. We also show that there exists a hierarchy in the class of apex NLC graph languages when we restrict the number of nonterminals in the right-hand sides of productions in apex NLC graph grammars. Received: 5 July 1994/12 February 1996     

Homogeneous grammars with a reduced number of non-context-free productions

A homogeneous production has its left-hand side formed by a non-empty string of identical nonterminals. A phrase-structure grammar is homogeneous if each of its productions is homogeneous. The present paper discusses the reduction of homogeneous grammars with respect to the number of non-context-free productions. More specifically, it demonstrates that for every phrase-structure grammar, there exists an equivalent homogeneous grammar that has only three non-context-free productions of the form 00→ε, 11→ε, and 22→ε.     

Linking theorems for tree transducers

Linear extended multi bottom-up tree transducers are presented in the framework of synchronous grammars, in which the input and the output tree develop in parallel by rewriting linked nonterminals (or states). These links are typically transient and disappear once the linked nonterminals are rewritten. They are promoted to primary objects here, preserved in the semantics, and carefully studied. It is demonstrated that the links computed during the derivation of an input and output tree pair are hierarchically organized and that the distance between (input and output) link targets is bounded. Based on these properties, two linking theorems are developed that postulate the existence of certain natural links in each derivation for a given input and output tree pair. These linking theorems allow easy, high-level proofs that certain tree translations cannot be implemented by (compositions of) linear extended multi bottom-up tree transducers.     

Nonterminals,homomorphisms and codings in different variations of OL-systems

Summary The use of nonterminals versus the use of homomorphisms of different kinds in the basic types of deterministic OL-systems is studied. A rather surprising result is that in some cases the use of nonterminals produces a comparatively low generative capacity, whereas in some other cases the use of nonterminals gives a very high generative capacity. General results are obtained concerning the use of erasing productions versus the use of erasing homomorphisms. The paper contains a systematic classification of the effect of nonterminals, codings, weak codings, nonerasing homomorphisms and homomorphisms for all basic types of deterministic OL-languages, including table 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.     

Scattered context grammars generate any recursively enumerable language with two nonterminals

By showing that two nonterminals are sufficient, we present the optimal lower bound on the number of nonterminals of scattered context grammars being able to generate any recursively enumerable language.     

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.     

One-sided random context grammars

The notion of a one-sided random context grammar is defined as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules. A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The paper demonstrates that without erasing rules, one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, these grammars characterize the family of recursively enumerable languages. In fact, these characterization results hold even if the set of left random context rules coincides with the set of right random context rules. Several special cases of these grammars are considered, and their generative power is established. In its conclusion, some important open problems are suggested to study in the future.     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.