Regular language. Proof

Question

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.

Answer 1

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$.