En este artículo se presentan algunas propiedades, ejemplos y contraejemplos del operador derivada formal con respecto a gramáticas independientes del contexto. Adicionalmente, se obtiene una ...relación entre la gramática G = { a → abr; b → br+1 } y números multifactoriales. Se obtienen algunas identidades sobre números multifactoriales mediante métodos gramaticales. In this paper some properties, examples and counterexamples about the formal derivative operator defined with respect to context-free grammars are presented. In addition, we show a connection between the context-free grammar G = { a → abr; b → br+1 } and multifactorial numbers. Some identities involving multifactorial numbers will be obtained by grammatical methods.
Assessing grammar Ball, Martin J; Crystal, David; Fletcher, Paul
2012., 2012, 2012-03-08, Letnik:
7
eBook
This collection is a resource book for those working with language disordered clients in a range of languages. It collects together versions of the well-known Language Assessment Remediation ...Screening Procedure (larsp) prepared for different languages. Starting with the original version for English, the book then presents versions in more than a dozen other languages. Some of these are likely to be encountered as home languages of clients by speech-language therapists and pathologists working in the uk, Ireland, the us and Australia and New Zealand. Others are included because they are major languages found where speech-language pathology services are provided, but where no grammatical profile already exists.
Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. In traditional regulated rewriting, the most ...interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on forbidding sets, i.e., a matrix is applicable to a sentential form w only if none of the words in its forbidding set occurs as a subword in w. This gives rise to further natural descriptional complexity measures: How long could words in forbidding sets be? How many words could be in any forbidding set? How many matrices contain non-empty forbidding contexts? As context-free grammars with forbidding sets are known as generalized forbidding grammars, we call this variant of matrix grammars also generalized forbidding. In this paper, we attempt to answer the four questions above while studying the computational completeness of generalized forbidding matrix grammars. In the course of our studies, we also define several new normal forms for type-0 grammars that might be of independent interest.
•Combining conditional matrix (KM) and generalized forbidding (GF) grammars, we define generalized forbidding matrix grammars.•We tackle the question how small measures of descriptional complexity could be while maintaining computational completeness.•Our studies also add new results to the theory of KM and of GF grammars.•We introduce a new normal form for type-0 grammars that was useful for us and that might be also of independent interest.
Grammars can serve as producers for structured test inputs that are syntactically correct by construction. A probabilistic grammar assigns probabilities to individual productions, thus controlling ...the distribution of input elements. Using the grammars as input parsers, we show how to learn input distributions from input samples, allowing to create inputs that are similar to the sample; by inverting the probabilities, we can create inputs that are dissimilar to the sample. This allows for three test generation strategies : 1) "Common inputs"-by learning from common inputs, we can create inputs that are similar to the sample; this is useful for regression testing. 2) "Uncommon inputs"-learning from common inputs and inverting probabilities yields inputs that are strongly dissimilar to the sample; this is useful for completing a test suite with "inputs from hell" that test uncommon features, yet are syntactically valid. 3) "Failure-inducing inputs"-learning from inputs that caused failures in the past gives us inputs that share similar features and thus also have a high chance of triggering bugs ; this is useful for testing the completeness of fixes. Our evaluation on three common input formats (JSON, JavaScript, CSS) shows the effectiveness of these approaches. Results show that "common inputs" reproduced 96 percent of the methods induced by the samples. In contrast, for almost all subjects (95 percent), the "uncommon inputs" covered significantly different methods from the samples. Learning from failure-inducing samples reproduced all exceptions (100 percent) triggered by the failure-inducing samples and discovered new exceptions not found in any of the samples learned from.
The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a ...particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian (“The independence of inherent ambiguity from complementedness among context-free languages”, JACM, 1966) on the non-closure of the unambiguous languages under complementation.
Triangular and Octagonal Array Grammars Kuberal, S.; Bhuvaneswari, K.; Kalyani, T.
Journal of physics. Conference series,
03/2021, Letnik:
1770, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Abstract
Hexagonal Array Grammars (HAG) were introduced by K.G. Subramanian 4. HAG increased the capacity of generating the hexagonal arrays on triangular grid. In this paper, using the Triangular ...Array Grammars (TAG) and Octagonal Array Grammars (OAG), we increasing the generative capacity for triangular and octagonal arrays. A system of the family of Triangular Array Language (TAL) and Octagonal Array Language (OAL) are presented.
In a recent paper (M. Barash, A. Okhotin, “An extension of context-free grammars with one-sided context specifications”, Inform. and Comput., 2014), the authors introduced an extension of the ...context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O(n4), where n is the length of the input string.
This article addresses the problem of suitably defining statistical models of languages derived from context-free grammars (CFGs), where the observed strings may be corrupted by noise or other ...mechanisms. This article uses the concept of a stochastic syntactic process (SSP), which we have introduced in previous work. An SSP is a stochastic process taking values in the set of all parse trees of a CFG. Inference problems such as estimating a parse tree for "noisy" processes are of obvious significance, particularly in the motivating example of metalevel target tracking. This article demonstrates that by careful application of the theory of probability, an SSP can be embedded into a Markov random field (MRF), thus opening up the possibility of the application of advanced machine learning algorithms based on graphical models to inference problems involving sophisticated target behavior at the "meta" level. This article provides a simple example of how a simple CFG can be embedded in an MRF. Extensions to context-sensitive grammars are discussed.
PDF
