converting to regular expression

Question

{w | w can be written as $0^k l 0^k$ for some $k \geq 1$ and for any $l$ in ${0,1}*}$

i.e. 00010111000 can be written as 0^3 10111 0^3

How can I convert this description into a regular expression?

Answer 1

My first solution was wrong. There is a clever trick at play here. Note that for $k\geq 1$, $$0^k\{0,1\}0^k=00^{k-1}\{0,1\}^\star 0^{k-1}0\subset 0\{0,1\}^\star0$$ since the $0^{k-1}$s can be absorbed into the Kleene star. Furthermore, it is obvious that $$0\{0,1\}^\star0\subset \bigcup_{k=1}^\infty 0^k\{0,1\}^\star 0^k.$$ Therefore $$\bigcup_{k=1}^\infty 0^k\{0,1\}0^k=0\{0,1\}^\star0$$ and hence the desired regular expression is $$0\{0,1\}^\star 0.$$