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.     

Fundamental methodological issues of syntactic pattern recognition

Fundamental open problems, which are frontiers of syntactic pattern recognition are discussed in the paper. Methodological considerations on crucial issues in areas of string and graph grammar-based syntactic methods are made. As a result, recommendations concerning an enhancement of context-free grammars as well as constructing parsable and inducible classes of graph grammars are formulated.     

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.     

模式识别中的递归结构及其句法-词义描述

模式的递归结构影响它的形式语言性质,成为模式结构描述的复杂问题之一.本文系统 地研究了递归结构的性质,按基本递归结构划分子模式,并以句法-词义方法对它们作分层文 法描述,从而建立了递归结构的有效描述体系.程序文法、属性文法以及由此派生的递归条件 文法和递归属性文法,都能成功地按此体系描述各种递归结构,这些文法的描述能力也因而得 到阐明.     

A representation of trees by languages I

A tree can be represented by a language consisting of a suitable coding of its finite branches. We investigate this representation and derive a number of reductions between certain equivalence problems for context-free tree grammars and recursive program schemes and the (open) equivalence problem for DPDA's. This is the first part of this work: it is devoted to technical results on prefix-free languages and strict deterministic grammars. Application to context-free tree grammars will be published in the second part.     

Adaptive star grammars and their languages

Motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. In adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. This mechanism makes adaptive star grammars more powerful than context-free graph grammars. Nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. In particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable.     

The covering problem for linear context-free grammars

Language equivalence, grammatical covering and structural equivalence are all notions of similarity defined on context-free grammars. We show that the problem of determining whether an arbitrary linear context-free grammar covers another is complete for the class of languages accepted by polynomially space bounded Turing machines. We then compare the complexity of this problem with the analogous problems for language equivalence and structural equivalence, not only for linear grammars, but also for regular grammars and unrestricted context-free grammars. As a step in obtaining the main result of this paper, we show that the equivalence problem for linear s-grammars is decidable in polynomial time.     

Context-free grammars with selective rewriting

Summary Selective substitution grammars first introduced by Rozenberg are further investigated. In particular we study context-free grammars with selection, since the original model is too general in its generative power. It is shown how the families of context-free, EOL and ETOL languages can be characterized by selective context-free grammars. Further the effect of linguistic restrictions on the family of selection languages is investigated. Finally, the notion of a universal grammar is investigated in this framework, demonstrating the existence of selection universal grammars under weak conditions on the selection family.Work supported partially by a Natural Sciences and Engineering Research Council of Canada grant No. A-7700 and partially by the Universitaire Instelling Antwerpen     

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.     

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.     

AN UNSUPERVISED INCREMENTAL LEARNING ALGORITHM FOR DOMAIN-SPECIFIC LANGUAGE DEVELOPMENT

While grammar inference (or grammar induction) has found extensive application in the areas of robotics, computational biology, and speech recognition, its application to problems in programming language and software engineering domains has been limited. We have found a new application area for grammar inference which intends to make domain-specific language development easier for domain experts not well versed in programming language design, and finds a second application in construction of renovation tools for legacy software systems. As a continuation of our previous efforts to infer context-free grammars (CFGs) for domain-specific languages which previously involved a genetic-programming based CFG inference system, we discuss extensions to the inference capabilities of GenInc, an incremental learning algorithm for inferring CFGs. We show that these extensions enable GenInc to infer more comprehensive grammars, discuss the results of applying GenInc to various domain-specific languages and evaluate the results using a comprehensive suite of grammar metrics.     

Self-embedded context-free grammars with regular counterparts

In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as and , that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain.Received: 17 January 2003, Published online: 17 February 2004Stefan Andrei: stefan@infoiasi.ro     

Spinal-Formed Context-Free Tree Grammars

In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks. Received May 29, 1998, and in revised form April 27, 1999, and in final form May 10, 1999.     

Grammatical inference: introduction and survey-part I

The problem of grammatical inference is introduced, and its potential engineering applications are demonstrated. Inference algorithms for finite-state and context-free grammars are presented. The application of some of the algorithms to the inference of pattern grammars in syntactic pattern recognition is illustrated by examples.     

An algebraic technique for context-sensitive parsing

A technique that represents derivations of a context-free grammarG over a semiring and that obtains for a wordw inL(G) the set of all canonical parses forw has previously been described. A state grammar is one of a collection of grammars that place restrictions on the manner of application of context-free-like productions and that generate a noncontext-free language. The context-free properties of a state grammar have been used to extend the algebraic parsing technique for languages generated by state grammars,viz., context-sensitive languages. The extension for state grammars is not unlike that required for other types of grammars in whose collection state grammars are representative.     

Learning context-free grammar using improved tabular representation

This paper describes an improved version of TBL algorithm [Y. Sakakibara, Learning context-free grammars using tabular representations, Pattern Recognition 38(2005) 1372–1383; Y. Sakakibara, M. Kondo, GA-based learning of context-free grammars using tabular representations, in: Proceedings of 16th International Conference in Machine Learning (ICML-99), Morgan-Kaufmann, Los Altos, CA, 1999] for inference of context-free grammars in Chomsky Normal Form. The TBL algorithm is a novel approach to overcome the hardness of learning context-free grammars from examples without structural information available. The algorithm represents the grammars by parsing tables and thanks to this tabular representation the problem of grammar learning is reduced to the problem of partitioning the set of nonterminals. Genetic algorithm is used to solve NP-hard partitioning problem. In the improved version modified fitness function and new delete specialized operator is applied. Computer simulations have been performed to determine improved a tabular representation efficiency. The set of experiments has been divided into 2 groups: in the first one learning the unknown context-free grammar proceeds without any extra information about grammatical structure, in the second one learning is supported by a partial knowledge of the structure. In each of the performed experiments the influence of partition block size in an initial population and the size of population at grammar induction has been tested. The new version of TBL algorithm has been experimentally proved to be not so much vulnerable to block size and population size, and is able to find the solutions faster than standard one.