Publication result detail

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

MEDUNA, A.; ZEMEK, P.

Original Title

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

English Title

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

Type

Peer-reviewed article not indexed in WoS or Scopus

Original Abstract

The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.

English abstract

The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.

Keywords

formal languages, context-free grammars, regular-controlled derivations, generation of sentences with their parses

Key words in English

formal languages, context-free grammars, regular-controlled derivations, generation of sentences with their parses

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2014

Released

27.02.2013

ISBN

0304-3975

Periodical

Theoretical Computer Science

Volume

477

Number

1

State

Kingdom of the Netherlands

Pages from

67

Pages to

75

Pages count

9

URL

http://www.sciencedirect.com/science/article/pii/S0304397513000066

BibTex

@article{BUT103400,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars",
  journal="Theoretical Computer Science",
  year="2013",
  volume="477",
  number="1",
  pages="67--75",
  doi="10.1016/j.tcs.2012.12.040",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S0304397513000066"
}