snippetMinor
How do I solve these questions regarding homomorphism?
Viewed 0 times
thesehomomorphismquestionsregardingsolvehow
Problem
Questions:
Questions to stack overflow:
- Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
- Now, give a second example of a homomorphism but this time using two different alphabets, Σ and Γ, for languages A and B, respectively.
Questions to stack overflow:
- How do I give the examples above? Do I make the state diagrams? Do I show it through the tuple-definition?
- What are some examples of the questions above?
Solution
Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$.
First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$.
The second is the map between words $$f':\Sigma^ \rightarrow \Gamma^$$.
The third is the map between languages $$f'':\mathbb{P}(\Sigma^) \rightarrow \mathbb{P}(\Gamma^)$$.
The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$. And $f$ is usually easier to describe directly than $f''$.
Another important observation is that not all function of type $$\mathbb{P}(\Sigma^) \rightarrow \mathbb{P}(\Gamma^)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.
First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$.
The second is the map between words $$f':\Sigma^ \rightarrow \Gamma^$$.
The third is the map between languages $$f'':\mathbb{P}(\Sigma^) \rightarrow \mathbb{P}(\Gamma^)$$.
The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$. And $f$ is usually easier to describe directly than $f''$.
Another important observation is that not all function of type $$\mathbb{P}(\Sigma^) \rightarrow \mathbb{P}(\Gamma^)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.
Context
StackExchange Computer Science Q#115992, answer score: 4
Revisions (0)
No revisions yet.