8
$\begingroup$

$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: enter image description here

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.