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