1
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ What is $L$ and why is it relevant. I mean, can't you just say "Let $\Sigma$ be an alphabet, $\forall \sigma \in \Sigma : $ (...) " ? $\endgroup$
    – Auberon
    Jan 23 '16 at 22:03
  • $\begingroup$ $L$ is some language. It is only relevant insofar as to give the reader the general idea of what the alphabet is used for, but it has no bearings on the meaning of the formula. At least not that I can see how it would. Regardless, I just copied more context around the formula in hopes to make it easier to answer the question. $\endgroup$
    – wvxvw
    Jan 23 '16 at 22:30
  • $\begingroup$ I think $2^{\Delta^*}$ is supposed the represent an uncountable set. The set of all possible languages over an alphabet $\Sigma$ is indeed an uncountable set. If what I think is correct, another notation for $2^{\Delta^*}$ is $\mathbb{P}(\Sigma)$. I'm not sure because I'm used to $2^{\aleph_0}$ for uncountable sets. Don't be confused though because since $\Sigma$ is a countable set, $Im(f)$ is countable as well, despite the co-domain of $f$ is uncountable. $\endgroup$
    – Auberon
    Jan 23 '16 at 22:48
  • 2
    $\begingroup$ It doesn't have any particular name. It's just a function mapping symbols to languages. $\endgroup$
    – Yuval Filmus
    Jan 23 '16 at 22:50
  • $\begingroup$ @YuvalFilmus well, it does in the book I'm reading from, this is why I asked. If it matters, the book calls this "הצבה", which literally translates into something like "substitution" or "positioning", in the sense as "making something stand in some place, possibly by force". $\endgroup$
    – wvxvw
    Jan 24 '16 at 6:33
5
$\begingroup$

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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Just to make sure, $1$ is the identity under concatenation, i.e. if talking about strings, that would be the empty string, am I right? $\endgroup$
    – wvxvw
    Jan 25 '16 at 11:47
  • 1
    $\begingroup$ Exactly. So for $A^*$ the identity is the empty word, and for $2^{B^*}$, the identity is the language $\{1\}$ containing only one word, the empty word. $\endgroup$
    – J.-E. Pin
    Jan 25 '16 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.