1
$\begingroup$

I'm not sure if I get the following definition right:

1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff:

  1. $\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \varphi(v)$
  2. $\varphi(\epsilon)=\{\epsilon\}$

My assumption: every string in $\Sigma^{*}$ with the size $>0$ maps to a Language from $\Delta^{*}$.

such as:

$\Sigma := \{a, b\}$, $\Delta:=\{0,1\}$

$\varphi(a) = \{01^{i}0 |i \in \mathbb N \}$, $\varphi(b) = \{w\in \Delta^{*} ||w|_{0} \neq |w|_{1}\}$

$\varphi(ab) = \varphi(a)\varphi(b)=\{01^{i}0w |i \in \mathbb N \land w \in \Delta^{*} |w|_{0} \neq |w|_{1}\}$

example strings: 001, 000, 0101, 01011, 010100, ...

My first question: Is this assumption and example right?

2.Def: $\varphi$ is finitie iff $\varphi(a)$ $\forall a \in \Sigma$ is a finite subset of $\Delta^{*}$

My assumption: $\Delta^{*}$ is every possible string over the alphabet $\Delta$ and an finite subset would be a limited set $X \subseteq \Delta^{*}$ $|X| < \infty$

I would now implie that my first example is not a finite substitution, because a and b are not mapping to finite sets.

an example could be:

$\varphi(a) = \{10^{i}1 | i \in \{1,...,100\}\}$, $\varphi(b) = \{\epsilon\}$

$\varphi(bba) = \varphi(b)\varphi(b)\varphi(a) = \{\epsilon\}\{\epsilon\}\{10^{i}1 | i \in \{1,...,100\}\}=\{10^{i}1 | i \in \{1,...,100\}\}$

now I can implie that the class $REG$ is closed under finite substitution, because a concatenation of finite sets is finite and every finite set is regular.

My second question: Is this my assumption about finite substitution and the closure propierty right?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You seem to have understood the operation of substitution. That maps any string into a language by concatenating the images of the letters.

Your argument that regular languages are closed under finite substitution does not work. Even if the substitution maps avery word into a finite language, the substitution of a regular language usually is infinite as the initial ragular language is infinite.

A possible approach is to use regular expressions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer! As you mentioned I forgot that usually a given language is already infinite. I'll try an example with an RE. $\endgroup$
    – xvzwx
    Mar 4, 2017 at 13:51
  • $\begingroup$ $L := \{ab^{n}a | n > 1\}$ The $RE$ would look like this: $RE_{L} = (ab^{+}a)$ $\varphi : \varphi(a)=\{100, 1100\}, \varphi(b)=\{1,0110\}$ $\Rightarrow \varphi(RE_{L}) = ((100(1 |0110)^{+}100) | (1100(1 |0110)^{+}100)|(1100(1 |0110)^{+}1100)|(100(1 |0110)^{+}1100))$ the resulting $RE$ is the combination of all words produced by the substitution. Conclusion: Iff the substitution is finite there is an $RE$ for the image of the mapping. $\endgroup$
    – xvzwx
    Mar 4, 2017 at 14:05
  • $\begingroup$ Npte that a formal proof needs mote than just an example or illustration. But I trust you have a good intuition now on what to explain in your proof. $\endgroup$
    – Hendrik Jan
    Mar 5, 2017 at 1:48

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.