Search results

1

On Normal Forms and Erasing Rules in Path Controlled Grammars

100%

Koutnŷ J., Meduna A.

Schedae Informaticae

|

2013

|

vol. 22

PL

This paper discusses path controlled grammars-context-free gram- mars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like normal forms for path controlled grammars-the first allows unit rules, the second allows just one erasing rule.

2

New Grammar Systems and Their Application Perspectives

100%

Horáček P., Meduna A.

Schedae Informaticae

|

2013

|

vol. 22

PL

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 translation.

3

On State-Synchronized Automata Systems

100%

Meduna A., Kučera J.

Schedae Informaticae

|

2015

|

vol. 24

PL

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n. In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

4

Some Power-Decreasing Derivation Restrictions in Grammar Systems

81%

Meduna A., Cermak M., Masopust T.

Schedae Informaticae

|

2010

|

vol. 19

PL

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase- structure grammars, controlled by the regular languages. The rst restriction requires that every production is always applied within the rst k nonterminals in every sentential form, for some k 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 dierent families of languages. Indeed, under the rst restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enumerable 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 -rules of nite index.

Refine search results

4 Schedae Informaticae

1 2015

2 2013

1 2010

4 Meduna A.

1 Cermak M.

1 Horáček P.

1 Koutnŷ J.

1 Kučera J.

1 Masopust T.

On Normal Forms and Erasing Rules in Path Controlled Grammars

New Grammar Systems and Their Application Perspectives

On State-Synchronized Automata Systems

Some Power-Decreasing Derivation Restrictions in Grammar Systems