For any language $L$ over $\Sigma^*$, define $$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$ In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.

An exercise in Sipser's book asks to show that $L_{1/2}$ is regular whenever $L$ is. I have seen two distinct solutions, and both involve an exponential blow-up of states.

Question: can anyone construct a family of languages $\{L_n\}$ such that the canonical automaton for $(L_n)_{1/2}$ is significantly (say, exponentially) larger than that for $L$? My best efforts so far only increase the state size by $+1$!

  • 1
    $\begingroup$ you dont mention the semiobvious issue of DFA minimization. havent seen the proofs but maybe they do not take it into acct. and a DFA minimization post-run on the proof construction might simplify the DFA significantly...? $\endgroup$
    – vzn
    Commented Feb 28, 2012 at 16:56
  • 5
    $\begingroup$ The constructions in the proofs are abstract and it's not at all clear how to minimize them via the standard techniques. $\endgroup$
    – Aryeh
    Commented Feb 28, 2012 at 18:49
  • $\begingroup$ Can you post the best family of languages you've found? $\endgroup$
    – didest
    Commented Feb 29, 2012 at 0:35
  • $\begingroup$ this is not reqd to answer your Q but it might be helpful to sketch out the constructions. another option is to attack the problem empirically with random FSMs $\endgroup$
    – vzn
    Commented Feb 29, 2012 at 1:38

1 Answer 1


See Mike Domaratzki's paper, State complexity of proportional removals



  • 2
    $\begingroup$ Excellent! theorem 6 gives a family of languages with $\Omega(e^{\sqrt{n\log n}})$ and theorem 3 gives an upper bound of $O(n e^{\sqrt{n\log n}})$, so there is little space for improvement. $\endgroup$
    – didest
    Commented Feb 29, 2012 at 2:34

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.