Regular language. Proof Let $L$ be regular language over $\{0,1\}$. Prove that $L'$ is also regular:
$$L' = \{ w | w \in L \mbox{ and  among words of length |w|, w is the least in lexicographic order.} \}$$
To explain, for example, if $ L = \{ 10001, 00001, 001,000\}$ then $L'= \{00001, 000\}$
Please hint me.
 A: Given $M=(\{0,1\}^*,Q,q_0,'\cdot',\{q_f\})$ a finite state automaton recognizing $L$, The idea of the proof is the following, given a word in $L'$ we run in parallel $M$ over all smaller  words then $w$ and if one of them reach the final state then the word is rejected otherwise we accept if it's accepted. 
so let's take $M'=\left\{\{0,1\right\}^*,Q',q_0', Q_f\}$:


*

*$Q'=Q\times 2^{Q}$ 

*$q'_0=q_0\times \emptyset$

*$Q_f=\left\{q_f\times S\big/ q_f\not \in S\right\}$


and the transition function is defined as follow:
$$\begin{align}\forall (q,S)\in Q'& : t((q,S),0)=(q.0,S.0)\\
  \forall (q,S)\in Q'& : t((q,S),1)=(q.1,S.1\cup \{q.0\})\end{align}$$
where $S.a=\{q.a\big/a\in S\}$
Given a word $w$ such that $M'(w)=(q,S)$,it's easy to see that $S$ contains exactly the set of states reached by $M$ over smaller words then the word $w$ and if this set contains $q_f$ this means that there exists a smaller word $w'$ such that $w'$ in $L$ and |w'|=|w| and this means that the automaton $M'$ must reject $w$ in this case, if $S$ deos not contain $q_f$ then the word $w$ is accepted iff $q=q_f$.
