**Problem Detail:**

Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows:

Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, where $L'$ is some language. I also met this definition: $f:\Sigma \to 2^{\Delta^*}$.

The reason I'm asking this is because I study in a language which is even more foreign to me than English, and it's hard to find what the terminology in the book means. I've only encountered this in connection to context-free languages, but since I don't really know what I'm looking at, I can't tell if that's something specific to them (my guess though is that it's not).

In the book I'm reading from, (which also happens to be in Hebrew) the word used to describe this concept is "הצבה", literally meaning "substitution" or "positioning", "fixing something in place".

###### Asked By : wvxvw

#### Answered By : J.-E. Pin

It looks like it refers to a *substitution*, but that the given definition is incomplete.

Anyway, in formal language theory, people often use monoid morphisms between free monoids. To avoid overloading the term "morphism", a monoid morphism from a free monoid $A^*$ into the monoid $2^{B^*}$ of languages of $B^*$ (under concatenation product of languages) is often called a *substitution*.

Now, since a morphism from $A^*$ into any monoid is entirely defined by the image of its letters, a substitution from $A^*$ to $B^*$ might be given as a map $\sigma: A \to 2^{B^*}$. But then it is extended to a map $A^* \to 2^{B^*}$ by setting $\sigma(1) = \{1\}$ and $\sigma(a_1 \dotsm a_n) = \sigma(a_1) \dotsm \sigma(a_1)$.

**Reference**. Page 5 in First four chapters of Berstel's book Transductions and Context-Free Languages, Teubner (1979). (Page 13 in the printed version)

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52188

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback