Let be a formal grammar. A pair of words over is said to correspond to the production if
for some words over . We also say that is a derivation step, and write .
Recall that a derivation in is a finite sequence of words
over such that , for . The derivation is also written
The derivation above has steps. Zero-step derivations are also permitted. These are just words over .
The reflexive transitive closure of is . Thus, means that there is a derivation starting with and ending with . There may be more than one derivation from to .
If we consider each production as a “letter” in the alphabet , then the above derivation can be represented by a “word” over in the following manner: the “word” is formed by taking concatenations of the “letters”, where concatenations correspond to successive applications of productions in :
Treating productions as “letters” is really nothing more than labeling each production with some symbol. Formally, call a labeling of an alphabet a surjection , where is some alphabet. For any , a label for is an element such that . We will only be interested in injective labeling (hence a bijection) from now on.
Definition. Suppose we are given a labeling of the set of productions in the grammar . Given a derivation , a derivation word for is defined inductively as follows:
if , then the empty word ,
if , then is a label for a production that corresponds to,
if , then , where
is a derivation word for the derivation ,
is a derivation word for the derivation .
If is a derivation word for derivation , let us abbreviate this by writing . Note that we are not applying the labeling to , it is merely a notational convenience.
A derivation word is sometimes called a control word, for it defines or controls whether and how a word may be derived from another word. Note that any may correspond to several distinct derivations, and hence several distinct derivation words. Also, the same derivation word may correspond to distinct derivations.
For example, let be a grammar over two symbols and with productions , , and ( generates the parenthesis language ) Label the productions as respectively. Then the derivation correspond to derivation words and . Notice that and both correspond to the derivation word .
Definition. The derivation language of a grammar is the set of all derivation words for derivations on words generated by . In other words, consider the labeling . The derivation language of is the set
The derivation language of is also called the Szilard language of , named after its inventor, and is denoted by .
For example, let be the grammar over a the letter , with productions given by , . If the productions are labeled , then . Note that . Likewise, if is the grammar over , with productions , , and , labeled respectively, then . However, is quite different from :
means the number of occurrences of in word ,
means that is a prefix of .
Remarks. Let be a formal grammar.
Some properties of :
is always context-sensitive.
If is regular, so is .
if is context-free, may not be; in fact, for any context-free language , there is a context-free grammar such that but is not context-free.
There exists a context-free language such that is not context-free for any grammar generating .
However, if one considers the subset of consisting of all derivation words corresponding to leftmost derivations, then is context-free.
It is an open question that, given any (context-sensitive) language , whether there is a grammar such that .
|Date of creation||2013-03-22 18:58:15|
|Last modified on||2013-03-22 18:58:15|
|Last modified by||CWoo (3771)|