2
$\begingroup$

I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, I don't understand how people come up with the substitution strings that they choose, and how they use them to produce a regular expression. Getting from the starting language to the final regular expression bewilders me.

For example, the following closure proof of an operation 'Quotient' written $L/R$, where $L$ and $R$ are regular languages:

$L/R = \{ x \mid \exists ~y \in R, \text{ where } xy \in L \}$
Define $\Sigma' = \{a' \mid a \in \Sigma\}$
Let $h(a) = a$
Let $h(a') = \lambda$
Let $g(a) = a'$
Let $f(a) = \{a, a'\}$
Then $L/R = h(f(L) ~\cap~ (\Sigma^* \cdot g(R)))$

What is the $a'$? Just another symbol? Why is that useful?
I don't understand the $f(a)$.
I don't understand what concatenating with $\Sigma^*$ yields.
I really don't understand much of it...

Can someone explain this to me in English, so I can better understand how to approach closure proofs of other operations?

$\endgroup$
  • $\begingroup$ You’re confusing homomorphisms and (regular) substitutions. They are not the same. A homomorphism maps a letter to a word. A (regular) substitution maps a letter to a (regular) language. $\endgroup$ – Yuval Filmus Feb 5 at 5:47
  • $\begingroup$ Ok. Very likely. My professor uses the terms interchangeably, so I've probably mixed them up for sure. $\endgroup$ – delrocco Feb 5 at 16:14
2
$\begingroup$

Prerequisite: you have to understand the basic techniques beforehand (or imagine/search/develop them on the fly).

A string homomorphism or simply a homomorphism maps each character to a single string (possibly in a different alphabet). For example, let $f(a)=ab$ and $f(b)=ba$. Then $f(ab)=abba$ and $(\{a, ab^2\})=\{ab, abbaba\}$.

A string substitution or simply a substitution is a mapping that maps each character to a language (possibly in a different alphabet). For example, let $f(a)=\{x\}$ and $f(b)=\{y, xz\}$. Then $f(ab)=\{xy,xxz\}$ and $f(\{a^2, b^2\})=\{x^2, y^2, yxz, xzy, xzxz\}$. The effect of substitution is not only changing the characters, but also including more variations. A substitution can be considered as the "union" of many homomorphisms.


Instead of explaining the formula $L/R = h(f(L) \cap (\Sigma^*\cdot g(R)))$, let us discover that formula by trial and error, starting from examining the target, $L/R$.

$L/R$ is made up by words each of which is the prefix of a word in $L$ whose remaining part is in $R$.

So, as a first step, given a word $w\in L$, we want to chop off a part of it. How to chop off a part? Mapping the letters to the empty string! Letting $h(a)=\lambda$, the empty word for all $a\in\Sigma$, we get $h(L)$.

Oh no! We just mapped every word in $L$ to the empty string! That is useless. What we want is to map a suffix that is in $R$ to empty string. For a word that looks like $xy\in L$, we want to chop off $y\in R$. How to carve out the suffixes? That means we should use intersection to target the remaining part. All words that end with a $y\in R$ are $\Sigma^*\cdot R$.

Now $L\cap \Sigma^*\cdot R$ are all the words in $L$ that end with a word in $R$.

Let us apply $h$ to it. Still, all of them are mapped to the empty string. We have to modify $h$ so that it will only map the letters in $R$ to empty string. Well, that is absurd since the letters in $R$ are the same as the letters used by $L$!

Wait. Let us suppose $R$ does use a different set of alphabet. For example, if $abc\in R$, we can imagine that actually means $a'b'c'\in R$. In other words, let us replace $R$ by $g(R)$, where $g(a)=a'$ for all $a\in\Sigma$.

Darn! Now $L\cap (\Sigma^*\cdot g(R))$ is empty. We need to change $L$ the the same way as $g$. Well then, it will not make any improvement. Is there a way to change $L$ to include the result of changing by $g$ as well as keeping itself intact?

String substitution comes to the rescue. We can let each letter in $L$ be itself or itself prime. This last ingenious touch almost concludes our journey. We have $h(f(L)\cap (\Sigma^*\cdot g(R))$.

What we got are all those suffixes in $g(R)$. However, we should become cautiously confident the solution is within reach since we get something non-trivial and strongly related.

In fact, all we need is letting $h$ preserve $a$ while erasing $a'$ instead. That is, $h(a)=a$ for all $a\in\Sigma$ and $h(a')=\lambda$. There remains some verification to do, but we have gone through the hard part of the journey.

Hopefully, you could gain some understanding if you have followed the above journey.


Here are two related exercises.

Exercise 1. Show that the left quotient $L\backslash R = \{ y \mid \exists x \in L \text{ such that } xy \in R \}$ is regular where $L$ and $R$ are regular. (In fact, the condition $L$ is regular is not necessary.)

Exercise 2. Let $L = \{ w \mid \text{odd}(w) \in L_1 \text{ and } \text{even}(w) \in L_2 \}$, where odd$(w)$ is the string of all letters of $w$ in odd positions and even$(w)$ is the string of all letters of $w$ in even positions. Show that $L$ is regular iff $L_1$ and $L_2$ are regular.

$\endgroup$
  • $\begingroup$ I have! Thank you. I wish you had taught me this instead. For Exercise 1, is this correct? (1) $\Sigma' = \{a' \mid a \in \Sigma\}~$ (2) $g(a) = a'~$ (3) $h(a) = a~$ (4) $h(a') = \lambda~$ (5) $f(a) = \{a,a'\}~$ (6) $h(g(R) \cdot \Sigma^* ~\cap~ f(L))$ $\endgroup$ – delrocco Feb 5 at 17:03
  • $\begingroup$ Exercise 1 is a simple mirror of your explanation, so it was easy (if I got it right). But Exercise 2 is certainly harder. I will attempt to tackle it. It is also closer to some of the problems I need to solve for an assignment. $\endgroup$ – delrocco Feb 5 at 17:07
  • $\begingroup$ Also, what are the extra bits of "verification" that you hinted at? And is the result that we are getting an actual regular expression, that can be used to show the resulting language is regular? Or are there additional steps to convert it to a true regular expression? $\endgroup$ – delrocco Feb 5 at 17:09
  • $\begingroup$ I've got a start on Exercise 2 and some questions. Do you want me to make a new question for that, or take it offline somewhere else? Thanks for your help. $\endgroup$ – delrocco Feb 5 at 17:27
  • $\begingroup$ Please come to the chat room I created for this question. $\endgroup$ – Apass.Jack Feb 5 at 23:02

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.