[Solved]: Is it possible to build DFA for odd-length words with 1 in the middle?

Problem Detail: 

$L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$

So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and after $1$. A limited DFA for the length less than 6:

How can I expand it so that it would accept any length words? Is it possible?

I tried putting cycles in it, but as I already said, then I just cant keep track of the number of chars after $1$ to be equal to that before. In other words 1 to be always in the middle.

Asked By : user8

Answered By : Martin Glauer

No, you can not. Proof by Pumping Lemma: Assume $L$ is regular and $n$ be the pumping length consider the word $w=0^n10^n$. Thus there are $x,y,z \in \{0,1\}^*$ with $|xy|<n$ and $|y| > 0$ such $xyz=w$. Then $\forall i\in \mathbb{N}_0: xy^iz \in L$.

But due to its length constraint $x$ and $y$ consist of $0$ only and all are before the $1$. Thus $xy^2z = 0^{n+|y|}10^n \notin L$.

Thus, $L$ is not regular and can not be expressed by any DFA.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56994