<p>Automata are not really needed to prove this result. Let $K$ be a regular language and let $R = \{w \in A^* \mid h^{-1}h(w) \subset K \}$. Then the complement of $R$ is $$R^c = \{w \in A^* \mid h^{-1}h(w) \cap K^c \not= \emptyset \} = h^{-1}h(K^c).$$ Since regular languages are closed under homomorphisms, inverse of homomorphisms and complementation, $R$ is regular. Now if $L$ is another regular language, the set $\{w \in L \mid h^{-1}h(w) \subset K \}$ is equal to $L \cap R$, which is regular as well.</p>

CC BY-SA 3.0
2014-08-24T09:39:25.917Z
2014-08-24T09:39:25.917Z
J.-E. Pin
<p>The answer is yes. To prove this, consider the complement language:
$$\{w: w\notin L(A) \vee \exists x: h(x)=h(w)\wedge x\notin L(B)\}$$</p>

<p>Now, we construct an NFA $C$ as follows. Given a word $w$, $C$ has $\overline{A}$ as a component, such that if $w\notin L(A)$ then $C$ accepts. It remains to check the rest.</p>

<p>Let $D$ be a DFA that recognizes $\overline{B}$.
In order to check if there exists a word $x$ as described, $C$ guesses (i.e. has a nondeterministic transition), for every letter $\sigma$ of $w$, a transition in $D$ that can be taken with a letter $\tau$ such that $h(\tau)=h(\sigma)$. The accepting states of this component are those of $D$.</p>

<p>It is not hard to prove that $C$ accepts the language above, and by complementing it you get an automaton for your desired language.</p>

CC BY-SA 3.0
2014-08-19T02:47:39.913Z
2014-08-19T02:47:39.913Z
Shaull
<p>Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$</p>

<p>Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted by $h$ as well. </p>

<p>Is the set 
$$\{w\in L(A)\mid h^{-1}(h(w))\subseteq L(B)\}$$ regular?</p>

CC BY-SA 3.0
2014-08-19T04:56:29.617Z
This seems like an a formal languages textbook exercise and more suitable for [cs.se]. Could you please explain your interest in the question?
Kaveh
<automata-theory><regular-language>
finite automata under morphism
user0928
# finite automata under morphism

(Asked by: username_0 on 2014-08-18)

Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$

Naturally $h$ can be extended to a mapping in $\Sigma^\*\rightarrow \Sigma'^\*$ which is denoted by $h$ as well.

Is the set
$$\{w\in L(A)\mid h^{-1}(h(w))\subseteq L(B)\}$$ regular?

**Tags:** automata-theory, regular-language
> **Comments:**
> **username_1**: This seems like an a formal languages textbook exercise and more suitable for [cs.se]. Could you please explain your interest in the question?  

---

## 2 answers

### Answer by username_2 on 2014-08-24. Score: 1

Automata are not really needed to prove this result. Let $K$ be a regular language and let $R = \{w \in A^\* \mid h^{-1}h(w) \subset K \}$. Then the complement of $R$ is $$R^c = \{w \in A^\* \mid h^{-1}h(w) \cap K^c \not= \emptyset \} = h^{-1}h(K^c).$$ Since regular languages are closed under homomorphisms, inverse of homomorphisms and complementation, $R$ is regular. Now if $L$ is another regular language, the set $\{w \in L \mid h^{-1}h(w) \subset K \}$ is equal to $L \cap R$, which is regular as well.


---

### Answer by username_3 on 2014-08-19. Score: 1

The answer is yes. To prove this, consider the complement language:
$$\{w: w\notin L(A) \vee \exists x: h(x)=h(w)\wedge x\notin L(B)\}$$

Now, we construct an NFA $C$ as follows. Given a word $w$, $C$ has $\overline{A}$ as a component, such that if $w\notin L(A)$ then $C$ accepts. It remains to check the rest.

Let $D$ be a DFA that recognizes $\overline{B}$.
In order to check if there exists a word $x$ as described, $C$ guesses (i.e. has a nondeterministic transition), for every letter $\sigma$ of $w$, a transition in $D$ that can be taken with a letter $\tau$ such that $h(\tau)=h(\sigma)$. The accepting states of this component are those of $D$.

It is not hard to prove that $C$ accepts the language above, and by complementing it you get an automaton for your desired language.


---

