3
$\begingroup$

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.

For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.

My thoughts so far are that replacing characters in a regular expression with regular expressions still gives us a regular expression overall. Namely I can show for $x \in L$ that $s(x)$ will be a regular set, and then I can do a union over $s(x)$ for all $x \in L$ to show $s(L)$ is regular (by closure of union).

My problem here is carefully showing the substitution will produce a regular set. Does it suffice to say if $x$ is something captured by a regular expression, then $s(x)$ is regular as well? I'm not sure how to prove this.

$\endgroup$
  • $\begingroup$ "where s is a substitution that replaces each symbol of each string in L with a regular expression". I am confused now, even although I thought I understood. Suppose $M$ is the language of only two words $\{ab, b\}$ over the alphabet $\{a, b\}$. Can you give an example of the said kind of substitution on $M$? $\endgroup$ – Apass.Jack Sep 30 '18 at 5:57
  • $\begingroup$ I can. Say the substitition is $a \mapsto ab^*a, b \mapsto (ab)^*$, then $M$ is mapped to the language described by $ab^*a(ab)^* \cup (ab)^*$. $\endgroup$ – reinierpost Oct 30 '18 at 13:10
  • 1
    $\begingroup$ GohanBlanco: You are mixing up regular expressions and regular languages. Please separate them carefully. $\endgroup$ – reinierpost Oct 30 '18 at 13:14
  • $\begingroup$ Hint: Construct an NFA for $s(L)$. $\endgroup$ – Raphael Dec 29 '18 at 11:17
2
$\begingroup$

First thing you must understand is that regular expression are closed under union(+), closure(*) and concatenation (.) . reason being every regex denotes a regular language and regular languages are closed under union, closure and concatenation.

Second thing you should know that if r1 and r2 are regex then the following regex are also regular

  1. r1 + r2
  2. r1.r2
  3. r1* ,r2*

so if you are substituting a regex by another regex it should fall among the above three categories or in simple words you will be able to form the regex(after substitution) with use of above relation. coming to you question the language generated after substitution can be formed using above closed properties over regex. let say r1 = a , r2 =b then we have

( ((r1.r2) * ) . r2* ) making it regular

one more thing the only operation defined to regex are the above three and if so any substitution of regex by regex will have either of the three operation associated with it thus making it regular again

$\endgroup$
  • $\begingroup$ Regular languages can be infinite, and the union of infinitely many regular languages isn't always regular, so you need another step. $\endgroup$ – reinierpost Oct 30 '18 at 13:15
  • $\begingroup$ @reinierpost yeah its correct but i have assumed that its understood in advance that number of operations used are finite as infinite sum( or union ) here makes little sense but when dealing with infinite union , generalisation seldomly holds $\endgroup$ – Noob Oct 30 '18 at 14:22
2
$\begingroup$

The easiest proof goes as follows:

Apply the substitution $s$ to a regular expression for $L$.

The proof is by routine induction. What we show inductively is that if $r$ is a regular expression then $$ L[s(r)] = s(L[r]), $$ where $L[r]$ is the language generated by the regular expression $r$.

$\endgroup$
1
$\begingroup$

For simplicity, let us fix the alphabet $\Sigma=\{a,b\}$.

$$E \to \phi \mid \epsilon \mid a \mid b \mid (E) \mid EE \mid (E)^* \mid (E\text{+}E)$$

The above context-free grammar generates the language of all regular expressions as a language over the alphabet $\Delta=\{\phi, \epsilon, a, b, (, ), {}^*, +\}$, according to the formal definition of regular expressions, where "+" denotes alternation.

Note that $\phi$ is the empty regular expression that generates the language that has no words, not even the empty word. The regular expression $\epsilon$ generates the language that has only one word, the empty word.

We have the following proposition.

(Recursive property of regular expressions) Let $F$ be a regular expression. Let $F'$ be $F$ but with one of the occurrences of the symbols in $\Sigma$ replaced by another regular expression $G$. For example, $F=aba^*$ and, if we replace the second $a$ by $(ba)$, we will obtain $F'=ab(ba)^*$. Then $F'$ is also a regular expression.

Proof. Suppose $F=uav$ where $u,v\in\Delta^*$ and $a$ is the occurrence as in the proposition. $w$ is obtained by a derivation tree which has a leaf node that corresponds to that $a$, whose parent node must be a node of the only non-terminal $E$. If we replace this derivation of $E\to a$ by the derivation tree of $E\to G$, we will obtain a derivation tree that generates $F'$. Done.


The above property can be understood simply as the following context-free grammar,

$E \to \phi \mid \epsilon \mid A \mid B \mid (E) \mid EE \mid (E)^* \mid (E\text{+}E)$
$A \to E \mid a$
$B \to E \mid b$

also generates the language of regular expressions.


Applying the above recursive property of the regular expressions multiple times, we obtain the claim in the question, which can be stated more formally as the following.

(Regular expressions closed under homomorphisms) Let $s$ be a map from $\Sigma$ to regular expressions. We can extend $s$ to all regular expressions naturally. Given any regular expression $E$, $s(E)$ is also a regular expression.

$\endgroup$

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.