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 new paradigm of syntactic pattern recognition, SPR, which uses multi-derivational parsing of vague languages is introduced in the paper. The methodology proposed addresses the issue of the ...recognition of vague/distorted patterns which is one of the important open problems in the area. The concept of the vague language of patterns and the efficient parsing method based on the class of dynamically programmed grammars are introduced. A vague language is defined with vague primitives which are vectors of "neighboring" primitives associated with measures of distance, probability, fuzziness, etc. The use of vague primitives allows us to identify <inline-formula><tex-math notation="LaTeX">b</tex-math> <mml:math><mml:mi>b</mml:mi></mml:math><inline-graphic xlink:href="flasinski-ieq1-3367245.gif"/> </inline-formula> best structural templates during multi-derivational parsing that can be used for getting more adequate final result. The generic architecture of SPR system based on the approach proposed together with the system's applications for short-term electrical load forecasting and for analysis of ultrasound images in order to diagnose congenital defects of fetal palates are presented. The results of the experimental studies are discussed.
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.
A context-free grammar with control language is a pair (G,R) where G is a context-free grammar and R is a regular set over the set of productions of G. Its language consists of all terminal words ...where the sequence of applied productions belongs to R.
We study context-free grammars with control languages belonging to subsets of the set of regular languages. We prove that we can obtain only context-free languages if we use regular commutative and strictly locally 1-testable languages. By strictly locally k-testable, k≥2, ordered, union-free, ordered, and regular circular control languages, we have no loss in the generative power, i.e., we generate the same family which is obtained by arbitrary regular control sets.
•Continuation of investigations the “power/simplification” of families of subregular languages.•Continuation of the work done by the author in the papers 3, 4, and 6.•Research related to papers by Salomaa from the sixties and seventies.•Result on commutative control languages is interesting since it differs from the results for other regulation mechanisms.
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.