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.     

On the number of components in cooperating distributed grammar systems

It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components.     

Parameter reduction and automata evaluation for grammar-compressed trees

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.     

可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言,证明了正规语言类是可交换上下文无关语言类的一个子集,而可交换上下文无关语言类是上下文无关语言类的一个子集;讨论了可交换上下文无关语言的结构特点,并给出了可交换上下文无关语言的Pumping引理。     

推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.     

On the structure of context-sensitive grammars

It is well known that the family of context-sensitive grammars generate languages which are not context-free and that it is undecidable whether a context-sensitive grammar generates a context-free language. However, the mechanism by which the use of context allows a non-context-free language to be generated is not well understood. In this paper we attempt to focus on this problem by surveying some of the results which speak to two questions: (i) What constraints can be placed on the form of the rules of context-sensitive grammars without restricting the weak generative capacity? (ii) What (nontrivial) constraints can be placed on the form of the rules of context-sensitive grammars such that only context-free languages will be generated?     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

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.     

An undecidable property of context-free linear orders

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

Context-free like restrictions on selective rewriting

Selective substitution grammars based on ‘context-free’ productions form a possible framework for the study of ‘grammatically oriented’ formal language theory. Such grammars (with no control governing the composition of derivation steps) are studied in this paper. In particular we study the effect of various conditions on selectors (which define the way that rewriting is performed); those conditions are aimed to formalize the notion of ‘using information about the context’ during the rewriting process. Each of them captures a particular feature of a rewriting according to a context-free grammar or an EOS system (essentially a context-free grammar that can also rewrite terminal symbols). Some of those conditions yield characterizations of the class of context-free languages for other conditions the lower and upper bound on the language generating power are given. Also a natural notion of a class of ‘simple’ rewriting systems is introduced (pattern grammars) and it is demonstrated that they possess surprisingly high language generating power.     

On the generative capacity of context-free matrix forms

This paper deals with the concepts of a matrix form and strict interpretation. By a matrix form we mean a context-free matrix grammar. Via an interpretation mechanism it generates a family of structurally related grammars and these generate a family of languages. We study here the properties of matrix forms as generators for the families of regular, linear and context-free languages. It is for instance shown that an arbitrary matrix form with only one nonterminal symbol does not generate the family of context-free languages if it contains a matrix with at least two productions.     

A system for recognizing online handwritten mathematical expressions by using improved structural analysis

A system for recognizing online handwritten mathematical expressions (MEs), by applying improved structural analysis, is proposed and experimentally evaluated on two databases. With this system, MEs are represented in the form of stochastic context-free grammar (SCFG), and the Cocke–Younger–Kasami (CYK) algorithm is used to parse two-dimensional (2D) structures of online handwritten MEs and select the best interpretation in terms of the results of symbol segmentation and recognition as well as structural analysis. A concept of “body box” is proposed, and two SVM models are applied for learning and analyzing structural relations from training patterns without the need for any heuristic decisions. Stroke order is used to reduce the complexity of the parsing algorithm. Even though SCFG does not resolve ambiguities in some cases, the proposed system still gives users a list of candidates that contains the expected result. The results of experimental evaluations of the proposed system on the CROHME 2013 and CROHME 2014 databases and on an in-house (“Hand-Math”) database show that the recognition rate of the proposed system is improved, while the processing time on a common CPU is kept to a practical level.     

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.     

On grammar forms with terminal context

Summary A context-free grammar form G defines a family of context-free grammars {ie397-01}(G). In this paper {ie397-02}(G) is extended to give the family of terminal context grammars {ie397-03}(G), which were introduced by Book [4]. It is shown that the families of languages defined by {ie397-04}(G) and {ie397-05}(G) are equal when G is an -free context-free grammar form. This generalizes the result of Book [4] for context-free grammars and underlines the usefulness of the notion of grammar forms in formal language theory.The work of the second author was carried out partially under a National Research Council of Canada Grant. No. A-7700 and partially under the auspices of the University of Karlsruhe     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

The undecidability of form equivalence for context-free and E0L forms

This paper studies the decidability status of various equivalence problems in form theory. Most of our discussions concern the notion of a language form. We compare the form equivalence problem between language forms with the ordinary equivalence problem between languages. However, the main results deal with L forms and grammar forms under strict interpretations. We prove that the form equivalence problem is undecidable for (a) context-free grammar forms, and (b) E0L forms. The proofs of these results are based on our investigations concerning language forms.     

Direction controlled programmed grammars

Summary A generalization of the notion of a context-free grammar is presented here. It is based on the notion of a programmed grammar. When the underlying context-free rules do not contain erasing, the class of languages obtained is identical with the class of context-sensitive languages. With underlying context-free rules containing erasing one obtains the class of recursively enumerable languages.The author is indebted to Drs. T. A. Zoethout for very useful discussions concerning this paper.