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.     

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.     

Left context precedence grammars

Summary Left context precendence grammars which are defined in this paper are a proper subclass of the precedence grammars and contain properly the simple precedence grammars. Left context precedence grammars need not be uniquely invertible. The parsing algorithm developed for left context precedence languages works with linear time and has the viable prefix property which is a stronger property than the correct prefix property.     

LR-parsing of extended context free grammars

Summary To improve the readability of a grammar it is common to use extended context free grammars (ECFGs) which are context free grammars (CFGs) extended with the repetition operator (^*), the alternation operator (¦) and parentheses to express the right hand sides of the productions. The topic treated here is LR-parsing of ECFGs. The LR(k) concept is generalized to ECFGs, a set of LR-preserving transformations from ECFGs to CFGs is given and finally it is shown how to construct LR-parsers directly from ECFGs.     

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.     

Evolutionary induction of stochastic context free grammars

This paper describes an evolutionary approach to the problem of inferring stochastic context-free grammars from finite language samples. The approach employs a distributed, steady-state genetic algorithm, with a fitness function incorporating a prior over the space of possible grammars. Our choice of prior is designed to bias learning towards structurally simpler grammars. Solutions to the inference problem are evolved by optimizing the parameters of a covering grammar for a given language sample. Full details are given of our genetic algorithm (GA) and of our fitness function for grammars. We present the results of a number of experiments in learning grammars for a range of formal languages. Finally we compare the grammars induced using the GA-based approach with those found using the inside-outside algorithm. We find that our approach learns grammars that are both compact and fit the corpus data well.     

On the descriptional complexity of scattered context grammars

This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.     

Learning deterministic context free grammars: The Omphalos competition

This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages. Editor: Georgios Paliouras and Yasubumi Sakakibara     

A survey of normal form covers for context free grammars

Summary An overview is given of cover results for normal forms of context-free grammars. The emphasis in this paper is on the possibility of constructing ɛ-free grammars, non-left-recursive grammars and grammars in Greibach normal form. Among others it is proved that any ɛ-free context-free grammar can be right covered with a context-free grammar in Greibach normal form. All the cover results concerning the ɛ-free grammars, the non-left-recursive grammars and the grammars in Greibach normal form are listed, with respect to several types of covers, in a cover-table.     

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.     

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.     

Incremental learning of context free grammars based on bottom-up parsing and search

This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by “inductive CYK algorithm,” mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form ww with w∈{a,b}⁺.     

Propagation of constraints along model transformations using triple graph grammars and borrowed context

Fundamental properties of model transformations based on triple graph grammars (TGGs) have been studied extensively including syntactical correctness, completeness, termination and functional behavior. But up to now, it is an open problem how domain specific properties that are valid for a source model can be preserved along model transformations such that the transformed properties are valid for the derived target model. This question shows up in enterprise modeling. Here, modeling activities related to different domains are handled by different parties, and their models need to be consistent and integrated into one holistic enterprise model later on. So, support for decentralized modeling processes is needed. One technical aspect of the needed support in this case is the (bidirectional) propagation of constraints because that enables one party to understand and check the constraints of another party. Therefore, we analyze in the framework of TGGs how to propagate constraints from a source model to an integrated model and, afterwards, to a target model, such that, whenever the source model satisfies the source constraint, also the integrated and target model satisfy the corresponding integrated and target constraint. In our main new results we show under which conditions this is possible.     

A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions.