3
$\begingroup$

Given a DFA $A = (Q, \Sigma, \delta, q_0, F)$ with $n$ states and a homomorphism $h: \Sigma \to \Gamma^*$. It is easy to see that the family of regular languages is closed under homomorphisms using regular expressions or by construction of a grammar.

My problem now is to analyze how many states are needed for a DFA $A' = (Q',\Gamma, \delta',q_0',F')$ to accept $h(L)$. First of all I tried to think of a basic construction method to get the automaton.

Let $a \in \Sigma$:

  1. If $h(a) = \varepsilon$ then all the transitions of $a$ in $A'$ can be removed.
  2. If $|h(a)| = 1$ then all the transitions with $a$ can be replaced with $h(a)$.

  3. If $|h(a)| \geq 2$ then the transition of $a$ in $A'$ has to be replaced with $h(a)$ and split into $|h(a)|-1$ states each with a one symbol transition

    a. If the prefixes of two unique symbols of $\Sigma$ do not share the same prefix then the resulting automaton can be extended into a DFA without adding any states(?).

    b. If prefixes are shared then the resulting automaton would be an NFA, therefore it has to be converted into a DFA (using power set construction) and minimizing it.

Therefore my estimation for the state complexity in case $3a$ would be: $$\begin{align*}|Q'| &\leq |Q| + |Q|\cdot\left(\sum_{a \in \Sigma} |h(a)| - 1\right)\\ &= |Q|\cdot(1- |\Sigma|+\sum_{a \in \Sigma} |h(a)| )\end{align*}$$

However, I'm not convinced about my construction as mentioned in step 3 and was not able to find an example of a language where the upper boundary is met. Therefore I'd be happy to see any advices.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't think your construction works; the automaton you construct might not be a DFA. For example, consider $h(a)=001$, $h(b)=0010$. $\endgroup$
    – D.W. ♦
    Commented Feb 17, 2017 at 21:25
  • $\begingroup$ @D.W. This is true, making step 3 only viable if and only if the homomorphic images are disjoint as mentioned in the formula. If they are not disjoint the only thing I can think of right now would be to construct the NFA, then convert it into a DFA (with potential exponential blow-up) and minimize it. $\endgroup$
    – PeterMcCoy
    Commented Feb 17, 2017 at 22:26
  • $\begingroup$ Disjoint doesn't mean what you (seem to) think it does. The condition in the question doesn't do what you (seem to) think it does. First of all, $h(a) \cap h(b)$ is meaningless, as $h(a)$ is an element of $\Gamma^*$, not a set; you can't take the intersection of two non-sets. Perhaps you meant $\{h(a)\}\cap \{h(b)\} = \emptyset$, but that's equivalent to $h(a) \ne h(b)$, which isn't enough. Second, 001 is disjoint from 0010 (since $001 \ne 0010$), so just requiring that the homomorphic images are disjoint doesn't make the problem go away. Things are a bit more complicated than that. $\endgroup$
    – D.W. ♦
    Commented Feb 18, 2017 at 0:49
  • $\begingroup$ @D.W. Disjoint is probably not the specific term, I was looking for. Let me reformulate what I mentioned before. Such a construction would only work out if $h(a)$ and $h(b)$ do not share the same prefix I.e. 001 and 0010 share the (non-proper) prefix 001, so that there won't be two transitions of the same symbol at the state. The homomorphic images can share the suffixes, which I previously would have forbidden with the word disjoint really meaning not sharing th e same sequence of letters in the homomorphic images. $\endgroup$
    – PeterMcCoy
    Commented Feb 18, 2017 at 10:19

1 Answer 1

Reset to default
1
$\begingroup$

Here is a simple construction that disproves your conjecture.

Let $a,b$ two relatively prime integers. It is known that the largest integer that cannot be represented as a non-negative integer combination of $a,b$ is $ab-a-b$.

Consider now the language $L = (0+1)^*$ and the homomorphism $h$ given by $h(0) = 0^a$ and $h(1) = 0^b$. Then $L$ is accepted by a one-state DFA, while $h(L)$ requires $ab-a-b+1$ states.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your counter-example in the general case, making the state complexity clear in this situation. I've forgot to edit the results of the discussion with D.W. in my question. That means what if the homomorphic images do not share the same prefix, since in your case the prefix of both images would be $0^{\min\{a,b\}}$ $\endgroup$
    – PeterMcCoy
    Commented Feb 18, 2017 at 16:18
  • 1
    $\begingroup$ If you have a different question, please ask it separately. We can't answer a moving target on this site. $\endgroup$
    – Yuval Filmus
    Commented Feb 18, 2017 at 16:21
  • $\begingroup$ I don't see where I asked a different question, it still is about state complexity of homomorphisms in general and in one specific case you disproved my conjecture but this did not answer my starting question yet. $\endgroup$
    – PeterMcCoy
    Commented Feb 18, 2017 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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