patternModerate
Is it possible to build DFA for odd-length words with 1 in the middle?
Viewed 0 times
dfathewithlengthwordspossibleformiddlebuildodd
Problem
$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.
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.
Solution
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| 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.
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.
Context
StackExchange Computer Science Q#56994, answer score: 13
Revisions (0)
No revisions yet.