0
$\begingroup$

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?

$\endgroup$

closed as off-topic by Kaveh, R B, David Eppstein, Hsien-Chih Chang 張顯之, Sasho Nikolov Aug 24 '14 at 16:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, R B, David Eppstein, Hsien-Chih Chang 張顯之, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This seems like an a formal languages textbook exercise and more suitable for Computer Science. Could you please explain your interest in the question? $\endgroup$ – Kaveh Aug 19 '14 at 4:56
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.