Detail publikace

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

MEDUNA, A. ZEMEK, P.

Originální název

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

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2013

Vydáno

27. 2. 2013

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Ročník

477

Číslo

1

Stát

Nizozemsko

Strany od

67

Strany do

75

Strany počet

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"
}