共查询到20条相似文献,搜索用时 593 毫秒
1.
Ronald V. Book 《International journal of parallel programming》1973,2(2):129-139
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? 相似文献
2.
3.
According to the classification of labelled graph grammars by Nagl [4], it can be shown that the class of context-sensitive graph languages is equivalent to the class of context-free graph languages and the context-free graph languages properly include the regular graph languages. 相似文献
4.
The class of languages expressible as the intersection ofk context-free languages is shown to be properly contained within the class of languages expressible as the intersection ofk + 1 context-free languages. Hence an infinite hierarchy of classes of languages is exhibited between the class of context-sensitive languages and the class of context-free languages. 相似文献
5.
Matej repinek Marjan Mernik Barrett R. Bryant Faizan Javed Alan Sprague 《Electronic Notes in Theoretical Computer Science》2005,141(4):99
In the area of programming languages, context-free grammars (CFGs) are of special importance since almost all programming languages employ CFG's in their design. Recent approaches to CFG induction are not able to infer context-free grammars for general-purpose programming languages. In this paper it is shown that syntax of a small domain-specific language can be inferred from positive and negative programs provided by domain experts. In our work we are using the genetic programming approach in grammatical inference. Grammar-specific heuristic operators and nonrandom construction of the initial population are proposed to achieve this task. Suitability of the approach is shown by examples where underlying context-free grammars are successfully inferred. 相似文献
6.
It is demonstrated that every context-free language is a homomorphic image of the intersection of two DOS languages and that every recursively enumerable language is the homomorphic image of the intersection of three DOS languages. It is also proved that by increasing the number of components in the intersections of DOS languages one gets an infinite hierarchy of classes of languages within the class of context-sensitive languages. 相似文献
7.
8.
Steffen Kopecki 《Theoretical computer science》2011,412(29):3629-3638
(Bounded) hairpin completion and its iterated versions are operations on formal languages which have been inspired by hairpin formation in DNA biochemistry. The paper answers two questions asked in the literature about iterated hairpin completion.The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion.In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular: actually, it is not context-free, but context-sensitive. 相似文献
9.
A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close
with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse
homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following
from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to
complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton
counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with
other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed. 相似文献
10.
Previous work on learning regular languages from exemplary training sequences showed that long short-term memory (LSTM) outperforms traditional recurrent neural networks (RNNs). We demonstrate LSTMs superior performance on context-free language benchmarks for RNNs, and show that it works even better than previous hardwired or highly specialized architectures. To the best of our knowledge, LSTM variants are also the first RNNs to learn a simple context-sensitive language, namely a(n)b(n)c(n). 相似文献
11.
Lane A. Hemaspaandra Proshanto Mukherji Till Tantau 《Information and Computation》2005,203(2):163-180
We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits’ own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such overhead-free machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead. 相似文献
12.
Derek Partridge 《Software》1985,15(12):1141-1158
Certain ambiguities in the definition of Pascal imperil the portability of Pascal programs. Specifications and an implementation of alternative interpretations are presented. Context-free grammars augmented with guarded commands are demonstrated as a notation for specifying the static context-sensitive constraints of programming languages. Most of the advantages of context-free grammars are preserved and yet the potential range of the syntactic definition component has been extended to encompass all static constraints. Context-sensitive syntax typically tends to either clutter the semantic definition component or (as with type equivalence in Pascal) result in undesirable implementor-dependent decisions. An implementation of a CFG-based parser that automatically checks for the defined context-sensitive constraints is also described. In addition stepwise abstraction is introduced as a practical technique for communicating formal programming language definitions. 相似文献
13.
P. F. Schuler 《Acta Informatica》1974,3(2):155-170
Summary An abstract family of formal languages containing context-free languages and properly contained in (deterministic) context-sensitive languages is introduced. This family is comprehensive enough to contain e.g. Algol 60 without admitting too complex recursive constructions possible in the frame of general context-sensitive languages.This family is essentially a family of property-languages, whereby the considered properties are restricted to properties which are constructively definable from a finite number of context-free sets. 相似文献
14.
《Information and Computation》2007,205(9):1387-1412
The class of growing context-sensitive languages (GCSL) was proposed as a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Growing context-sensitive languages and their deterministic counterpart called Church–Rosser languages (CRL) complement the Chomsky hierarchy in a natural way, as the classes filling the gap between context-free languages and context-sensitive languages. They possess characterizations by a natural machine model, length-reducing two-pushdown automata (lrTPDA). We introduce a lower bound technique for lrTPDAs. Using this technique, we prove the conjecture of McNaughton, Narendran and Otto that the set of palindromes is not in CRL. As a consequence we obtain that CFL∩coCFL as well as UCFL∩coUCFL are not included in CRL, where UCFL denotes the class of unambiguous context-free languages; this solves an open problem posed by Beaudry, Holzer, Niemann and Otto. Another corollary is that CRL is a strict subset of GCSL∩coGCSL. 相似文献
15.
《IEEE transactions on pattern analysis and machine intelligence》1977,(2):105-124
This paper presents the formalism of Production Systems and investigates its applcation to defe the Syntax and trlation of programming languages. Several properties appear well-suited to this task: 1) the formalism can be used to specify exactly the syntax of a computer language, including context-sensitive requirements; 2) the specification of the context-sensitive requirements on syntax can be isolated from the context-free requirements; 3) the same formalism can be used to specify more general structural properties, including the translation of one language into another. The notation has been developed with readabifity as a prime designissue. The following examples are given:1) aspecificationofthesyntaxofasmallbutdifflcultsubset of PL/I;2) a specification of the rules for translating lambda-culus expressions into, normal form. 相似文献
16.
17.
Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational capacity of reversible computations in pushdown automata is investigated and turns out to lie properly in between the regular and deterministic context-free languages. Furthermore, it is shown that a deterministic context-free language cannot be accepted reversibly if more than realtime is necessary for acceptance. Closure properties as well as decidability questions for reversible pushdown automata are studied. Finally, we show that the problem to decide whether a given nondeterministic or deterministic pushdown automaton is reversible is P-complete, whereas it is undecidable whether the language accepted by a given nondeterministic pushdown automaton is reversible. 相似文献
18.
Kathi Fisler 《Journal of Logic, Language and Information》1999,8(3):323-361
Timing diagrams are popular in hardware design. They have been formalized for use in reasoning tasks, such as computer-aided verification. These efforts have largely treated timing diagrams as interfaces to established notations for which verification is decidable; this has restricted timing diagrams to expressing only regular language properties. This paper presents a timing diagram logic capable of expressing certain context-free and context-sensitive properties. It shows that verification is decidable for properties expressible in this logic. More specifically, it shows that containment of -regular languages generated by Büchi automata in timing diagram languages is decidable. The result relies on a correlation between timing diagram and reversal bounded counter machine languages. 相似文献
19.
Recently the one-counter trace languages and the context-free trace languages have been characterized through restricted types of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size one (so-called stl-det-R(1)-automata) that work in mode ‘=1’ and that use an external counter or pushdown store to determine the successor components within computations. Here we study the deterministic variants of these CD-systems, comparing the resulting language classes to the classes of languages defined by CD-systems of stl-det-R(1)-automata without such an external device and to some classical language families, among them in particular the classes of rational, one-counter, and context-free trace languages. In addition, we present a large number of (non-)closure properties for our language classes. 相似文献