.so tmac.ilib
.TH CSGEN 1 "The University of Arizona \- 6/28/83"
.SH NAME
csgen \- context-sensitive sentences
.SH SYNOPSIS
\f3csgen\fP [\f3\-t\fR]
.SH DESCRIPTION
\fICsgen\fR accepts a context sensitive production grammar from standard
input and generates randomly selected sentences from the corresponding
language.
.PP
Uppercase letters stand for nonterminal symbols, \*M\->\fR indicates the
lefthand side can be rewritten by the righthand side. Other characters
are considered to be terminal symbols. Lines beginning with \*M#\fR
are considered to be comments and are ignored.
A line consisting of a nonterminal symbol followed by a colon and
a nonnegative integer \*Mi\fR is a generation specification for \fIi\fR
instances of sentences for the language defined by the nonterminal
(goal) symbol.
An example is:
.DS
#   a(n)b(n)c(n)
#   Salomaa, p. 11.  Attributed to M. Soittola.
#
X
X\->abc
X\->aYbc
Yb\->bY
Yc\->Zbcc
bZ\->Zb
aZ\->aaY
aZ\->aa
X:10
.DE
A positive integer followed by a colon can be prefixed to a production
to replicate that production, making its selection more likely. For
example,
.DS
3:X\->abc
.DE
is equivalent to
.DS
X\->abc
X\->abc
X\->abc
.DE
.PP
The \f3\-t\fR option writes a trace of the derivations to standard 
error output.
.SH LIMITATIONS
Nonterminal symbols can only be represented by single uppercase letters
and there is no way to represent uppercase terminal symbols.
.PP
There can be only one generation specification and it must appear as
the last line of input.
.PP
Generation of context-sensitive strings is a slow process. It may not
terminate, either because of a loop in the rewriting rules of the
grammar or because of the progressive accumulation of nonterminal symbols. \fICsgen\fR,
however, avoids deadlock, in which there are no possible rewrites for
a string in the derivation.
.bp
.SH SEE ALSO
Salomaa, Arto. \fIFormal Languages\fR, Academic Press, New York, 1973.
.SH AUTHOR
Ralph E. Griswold