Wyniki wyszukiwania - BazTech

1

Generative Capacity of Contextual Grammars with Subregular Selection Languages

Truthe Bianca

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 1-2

123--150

EN

A contextual grammar is a language generating mechanism inspired by generating sentences in natural languages. An existing string can be extended to a new string of the language by adjoining a context before and behind the string or by inserting it into the string around some subword. The first mode is called external derivation whereas the second mode is called internal derivation. If conditions are given, around which words which contexts can be adjoined, we speak about contextual grammars with selection. We give an overview about the generative capacity of contextual grammars (working externally or internally) where the selection languages belong to subregular language classes. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We compare such families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages, or based on languages defined by restrictions regarding the descriptional complexity.

2

New Grammar Systems and Their Application Perspectives

Horáček P., Meduna A.

Schedae Informaticae

|

2013

|

Vol. 22

47--68

EN

This paper presents new grammar systems that describe transfor- mations of syntactic structures. They represent two approaches: synchronous grammars and transducers. The systems consist of well-known models such as context-free grammars and finite automata. Particular attention is paid to synchronization of regulated grammars. The paper recalls formal definitions of the systems and discusses theoretical results regarding their generative and accepting power. The last part briefly introduces application perspectives in natural language translation, illustrated by examples of Czech-English trans- lation.

3

Left Random Context ET0L Grammars

Meduna A., Zemek P.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 3

289--304

EN

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.

4

Synchronous versions of regulated grammars : generative power and linguistic applications

Horáček P., Meduna A.

Theoretical and Applied Informatics

|

2012

|

Vol. 24, No. 3

175-190

EN

This paper introduces the notion of new synchronous grammars as systems consisting of two context-free grammars with linked rules instead of linked nonterminals. Further, synchronous versions of regulated grammars, specifically, matrix grammars and scattered context grammars, are discussed. From a theoretical point of view, this paper discusses the power of these synchronous grammars. It demonstrates the following main results. First, if we synchronize context-free grammars by linking rules, the grammar generates the languages defined by matrix grammars. Second, if we synchronize matrix grammars by linking matrices, the generative power remains unchanged. Third, synchronous scattered context grammars generate the class of recursively enumerable languages. From a more practical viewpoint, this paper presents linguistic application prospects. The focus is on natural language translation between Japanese and English.

5

On the Generative Power of !-Grammars and ω-Automata

Chen Z.

Fundamenta Informaticae

|

2011

|

Vol. 111, nr 2

119-145

EN

An ω-grammar is a formal grammar used to generate ω-words (i.e. infinite length words), while an ω-automaton is an automaton used to recognize ω-words. This paper gives clean and uniform definitions for ω-grammars and ω-automata, provides a systematic study of the generative power of ω-grammars with respect to ω-automata, and presents a complete set of results for various types of ω-grammars and acceptance modes. We use the tuple (σ, ρ, π) to denote various acceptance modes, where σ denotes that some designated elements should appear at least once or infinitely often, ρ denotes some binary relation between two sets, and π denotes normal or leftmost derivations. Technically, we propose (σ, ρ, π)-accepting ω-grammars, and systematically study their relative generative power with respect to (ρ,π)-accepting ω-automata. We show how to construct some special forms of ω-grammars, such as ε-production-free ω-grammars. We study the equivalence or inclusion relations between ω-grammars and ω-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of ω-CFG is strictly weaker than ω-PDA, and the generative power of ω-CSG is equal to ω-TM (rather than linearbounded ω-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes.

6

Some power - decreasing derivation restrictions in grammar systems

Meduna A., Čermák M., Masopust T.

Schedae Informaticae

|

2010

|

Vol. 19

23-34

EN

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by the regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k greather than 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate different families of languages. Irideed, under the first restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enu-merable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without e-rules of finite index.

7

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

Masopust T.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 4

473-480

EN

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.

8

Monocultures and Homogeneous Environment in Eco-Grammar Systems

Kelemenová A., Tupý M.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

349-365

EN

Two special cases of eco-grammar systems are studied, namely the systems with identical agents, called monocultures and the systems with homogeneous environment characterized by a unary alphabet. The generative power of these eco-grammar systems, given by the languages of the environments, is discussed. Introduced special cases restrict the generative power of eco-grammar systems. Hierarchy or incomparability of language classes with respect to the degree of eco-grammar systems, given by the number of the agents, is shown for various cases of eco-grammar systems.

9

The synergy in cooperating grammar systems

Staniszkis M.

Zeszyty Naukowe Uniwersytetu Jagiellońskiego. Prace Informatyczne

|

2000

|

z. 10

165-179

EN

The study of multiagent distributed systems through the optics of the theory of formal grammars and languages is presented. Models based on NLC and BNLC graph grammars are mainly considered. The basic intuition of a grammar model of distributed systems follows the blackboard model for problem solving and is the following: component grammars forming the distributed system execute rewritings on a shared sentential form/graph. The order of participation on rewriting, the start and stop conditions of participation are determined by the strategies for the cooperation of components. The strategies of cooperation considered include the ones based on chains or linear, partial and arbitrary orders control relations. The introduced transformations on graphs representing the control permit one to obtain results regarding the synergy created by the cooperation.