共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
Anton Nijholt 《Theoretical computer science》1979,9(3):287-309
A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar.Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented. 相似文献
3.
《Theoretical computer science》2005,340(2):257-272
Tile rewriting grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into an isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to context-free grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the tiling systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context-free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals. 相似文献
4.
Frank Drewes Berthold Hoffmann Dirk Janssens Mark Minas 《Theoretical computer science》2010,411(34-36):3090-3109
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. 相似文献
5.
6.
V. V. Gribova A. S. Kleschev D. A. Krylov 《Automatic Documentation and Mathematical Linguistics》2013,47(2):59-67
A mathematical apparatus for describing the context-free grammars of artificial languages is presented: the syntax of the language to describe them is defined, as well as logical and generative semantics, and examples are provided to show how the suggested apparatus can be used. 相似文献
7.
We consider XML documents described by a document type definition (DTD). An XML-grammar is a formal grammar that captures
the syntactic features of a DTD. We investigate properties of this family of grammars. We show that every XML-language basically
has a unique XML-grammar. We give two characterizations of languages generated by XML-grammars, one is set-theoretic, the
other is by a kind of saturation property. We investigate decidability problems and prove that some properties that are undecidable
for general context-free languages become decidable for XML-languages. We also characterize those XML-grammars that generate
regular XML-languages.
Received: 16 March 2001 / 19 March 2002 相似文献
Résumé. Nous considérons des documents XML décrits par une définition de type de document (DTD). Une grammaire XML est une grammaire formelle qui retient les aspects syntaxiques d'une DTD. Nous étudions les propriétés de cette famille de grammaires. Nous montrons qu'un langage XML a essentiellement une seule grammaire XML. Nous donnons deux caractérisations des langages engendrés par les grammaires XML, la première est ensembliste, la deuxième est par une propriété de saturation. Nous examinons des problèmes de décision et nous prouvons que certaines propriétés qui sont indécidables pour les langages context-free généraux deviennent décidables pour les langages XML. Nous caractérisons également les grammaires XML qui engendrent des langages rationnels.
Received: 16 March 2001 / 19 March 2002 相似文献
8.
Jan Pittl 《Theoretical computer science》1981,16(2):149-175
The paper studies the family of LLP(k) grammars introduced by Lomet. Two new grammatical characterizations for this class are presented. The first one shows that these grammars form an extension of strict deterministic grammars, in particular, any strict deterministic grammar is an LLP(0) one. LLP(k) grammars share with this subclass many important mathematical properties. The second characterization proves LLP(k) grammars to be a natural cross between LL(k) and LR(k) grammars. Relationships between corresponding families of languages are also investigated. 相似文献
9.
10.
Many different definitions for LR(k) grammars exist in the literature. One of these definitions is chosen and many important implications are drawn from it. In particular, the LR(k) characterization theorem provides valuable information about chains of derivations. The LR(0) languages are then characterized by acceptance by deterministic pushdown automata with a special termination condition, by a condition on the strings in the language, and set theoretically. Important closure properties of the LR(0) languages and a related class of languages are then examined. These are used to examine some decidability questions relating to the class of LR languages. One of these questions is shown to be equivalent to the equality problem for deterministic pushdown automata.A survey of other LR(k) definitions is given and the exact differences are characterized. On the basis of this analysis, justification for the choice of definition used here is provided. 相似文献
11.
12.
13.
Martti Penttonen 《Acta Informatica》1974,3(3):285-291
Summary A derivation language associated with a context-free grammar is the set of all terminating derivations. Hierarchy and closure properties of these languages are considered. In addition to the formerly known solvability of the emptiness and finiteness problems the equivalence problem is shown to be solvable for derivation languages. 相似文献
14.
This paper surveys what is currently known about natural language morphology and syntax from the perspective of formal language theory. Firstly, the position of natural language word-sets and sentence-sets on the formal language hierarchy is discussed. Secondly, the contemporary use by linguists of a range of formal grammars (from finite state transducers to indexed grammars) in both word-syntax (i.e. morphology) and sentencesyntax is sketched. Finally, recent developments such as feature-theory, the use of extension and unification, default mechanisms, and metagrammatical techniques, are outlined. 相似文献
15.
《国际计算机数学杂志》2012,89(4):277-285
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. 相似文献
16.
17.
We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for
this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is formally mapped to semantics
given in terms of a ring of operators, so that composition of grammars corresponds to operator addition or multiplication.
The operators are generators for the time-evolution of stochastic processes. The dynamical evolution occurs in continuous
time but is related to a corresponding discrete-time dynamics. An expansion of the exponential of such time-evolution operators
can be used to derive a variety of simulation algorithms. Within this modeling framework one can express data clustering models,
logic programs, ordinary and stochastic differential equations, branching processes, graph grammars, and stochastic chemical
reaction kinetics. The mathematical formulation connects these apparently distant fields to one another and to mathematical
methods from quantum field theory and operator algebra. Such broad expressiveness makes the framework particularly suitable
for applications in machine learning and multiscale scientific modeling.
相似文献
18.
19.
20.
Salvatore La Torre Margherita Napoli Mimmo Parente 《Formal Methods in System Design》2007,31(3):265-279
Visibly pushdown languages are an interesting subclass of deterministic context-free languages that can model nonregular properties
of interest in program analysis. Such class properly contains typical classes of parenthesized languages such as “parenthesis”,
“bracketed”, “balanced” and “input-driven” languages. It is closed under boolean operations and has decidable decision problems
such as emptiness, inclusion and universality. We study the membership problem for visibly pushdown languages, and show that
it can be solved in time linear in both the size of the input grammar and the length of the input word. The algorithm relies
on a reduction to the reachability problem for game graphs. We also discuss the time complexity of the membership problem
for the class of balanced languages which is the largest among those cited above. Besides the intrinsic theoretical interest,
we further motivate our main result showing an application to the validation of XML documents against Schema and Document
Type Definitions (DTDs).
Work partially supported by funds for the research from MIUR 2006, grant “Metodi Formali per la verifica di sistemi chiusi
ed aperti”, Università di Salerno.
A preliminary version of this paper was published in the Proceedings of the 4th International Symposium Automated Technology
for Verification and Analysis (ATVA 2006), Lecture Notes in Computer Science 4218, pp. 96–109, 2006. 相似文献