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)     

An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages.In this paper an LR parsing technique for extended context-free grammars is presented, which is based on an underlying transformation of the grammar into an equivalent context-free one.The technique is suitable for inclusion in one-pass compilers: the implementation requires little extensions to the algorithms working for normal LR grammars. Besides describing the parsing method, the paper shows also the algorithms for deriving the parsing tables; tables optimization is also discussed. Finally, this technique is compared with other proposals appeared in the literature.     

A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

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.     

Ll-regular grammars

Culik II and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars.

In this paper we consider an analogous extension of the LL(k) grammars called the LL- regular grammars. The relation of this class of grammars to other classes of grammars will be shown. Any LL-regular grammars is an LR-regular grammar. Properties of LL(k) grammars can be generalized to properties of LL-regular grammars.     

Inference for transition network grammars

This paper gives a brief introduction to transition networks and proposes an approach to the inference of transition network grammars.     

A CKY parser for picture grammars

We study the complexity of the membership or parsing problem for pictures generated by a family of picture grammars: Siromoney's Context-Free Kolam Array grammars (coincident with Matz's context-free picture grammars). We describe a new parsing algorithm, which extends the Cocke, Kasami and Younger's classical parsing technique for string languages and preserves the polynomial time complexity.     

Workspace for disabled people

The paper aims at determining the workspace for disabled young people. The investigation embraced a group of young people with motor dysfunction of lower extremities. Seventeen measurements were taken of 32 boys and 45 girls aged 15-18. There are significant differences in functional, dimensions of the arm between the healthy and the disabled populations. The differences clearly indicate that there is a need for different shaping of space in which people of limited motor efficiency must function. A method based on Das and Grady's concept was used in determining workspace. This method was modified by the author. The method allows determination of workspace by means of several simple anthropometric measurements. Workspace for young people investigated was determined for the sitting position in transverse and sagittal planes. The results of the investigation constitute data for design and estimation of workplaces for disabled young people with motor dysfunction of lower extremities. The results can also be used to determine functional space in classrooms, school workshops, educational and rehabilitation centres.     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

On the languages generated by context-sensitive fuzzy grammars

It is proved that the family of the languages generated by 1-fold fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is equal to the family of the context sensitive languages. Also, one shows that the family of the languages generated by fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is included in the family of the context-sensitive languages.     

Lower bounds for context-free grammars

Ellul, Krawetz, Shallit and Wang prove an exponential lower bound on the size of any context-free grammar generating the language of all permutations over some alphabet. We generalize their method and obtain exponential lower bounds for many other languages, among them the set of all squares of given length, and the set of all words containing each symbol at most twice.     

Feature grammars for semantic analysis

In this paper, we present a formalism called feature grammar and its application to several problems of semantic analysis. Our extension concerns the structure of the feature value sets, which can be complex, and the definition of unification, which is dependent on this structure. Moreover, we introduce generation rules for feature symbols in order to determine well-formed symbols, which form the alphabet of a formal language for natural language analysis.     

Parsers for indexed grammars

Three classes of parsable indexed grammars are defined. The new parsing mechanisms are derived by extending those that have been most successful for contextfree grammars, the LR and LL algorithms. Design criteria for the new grammar classes include membership decidability and unambiguity. We show that all three parsers operate in linear time for at least some grammars in our new classes. One of our new classes generates all the deterministic contextfree languages, along with some noncontextfree languages. We also show that the flag strings generated by indexed grammars are regular sets. This is done by showing that they can be generated by regular canonical systems.