Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.     

Abstract families of context-free grammars

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)     

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.     

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.     

Generalized one-sided forbidding grammars

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.     

On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy.     

Semantic equivalence of covering attribute grammars

This paper investigates some methods for proving the equivalence of different language specifications that are given in terms of attribute grammars. Different specifications of the same language may be used for different purposes, such as language definition, program verification, or language implementation. The concept of syntactic coverings is extended to the semantic part of attribute grammars. Given two attribute grammars, the paper discusses several propositions that give sufficient conditions for one attribute grammar to be semantically covered by the other one. These tools are used for a comparison of two attribute grammars that specify syntax and semantics of mixed-type expressions. This example shows a trade-off between the complexity of syntactic and semantic specifications. Another example discussed is the equivalence of different attribute grammars for the translation of the while-statement, as used in compilers for top-down and bottom-up syntax analysis.This work was in part supported by the National Research Council of Canada.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.     

A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars

We provide a strongly polynomial algorithm for determining whether a given multi-type branching process is subcritical, critical, or supercritical. The same algorithm also decides consistency of stochastic context-free grammars.     

One application of real-valued interpretation of formal power series

We define two natural properties of context-free grammars. The first property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.     

A model for the formal definition of programming languages

An operational model which allows the complete formal definition of the full syntax and, particularly, semantics of programming languages is described. Both its syntactic and semantic parts are based on so-called linked-forest manipulation systems which allow the definition of mappings on forests. The idea of “linking” is crucial for the given model, we represent not only abstract programs but also intermediate states of our system (abstract computer) by labelled forests with pointers.     

Fractal encoding of context-free grammars in connectionist networks

Connectionist network learning of context-free languages has so far been applied only to very simple cases and has often made use of an external stack. Learning complex context-free languages with a homogeneous neural mechanism looks like a much harder problem. The current paper takes a step toward solving this problem by analyzing context-free grammar computation (without addressing learning) in a class of analog computers called dynamical automata, which are naturally implemented in connectionist networks. The result is a widely applicable method of using fractal sets to organize infinite-state computations in a bounded state space. An appealing consequence is the development of parameter-space maps, which locate various complex computers in spatial relationships to one another. An example suggests that such a global perspective on the organization of the parameter space may be helpful for solving the hard problem of getting connectionist networks to learn complex grammars from examples.