Regular expression for binary words with 1 in the middle

Question

Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$

I'm having trouble finding a solution for this regular expression. I think it's impossible because you need to have an even amount of 1's and 0's on both sides of the middle 1. You also would need to have the same amount of 1's and 0's on both sides. Since a regular expression has limited memory, would that make this regular expression impossible?

Answer 1

The intersection of your language with $0^*10^*$ is $\{ 0^n 1 0^n : n \geq 0 \}$, which can be shown to be non-regular by reduction to the more well-known $\{ a^n b^n : n \geq 0 \}$. This shows that your language indeed isn't regular.

Answer 2

Yes, you are right that there is no regular expression for this language.

For the sake of contradiction, assume $L$ is regular with pumping length $p$. Consider the word $w=0^p1^{n+1}$. There must be $x,y,z \in \{0,1\}^*$ such that $|xy|<p$, $|y| > 0$, $w=xyz$ and for all nonnegative integer $i$, $xy^iz \in L$.

Since $w$ starts with $p$ 0's and $xy$ is shorter than $p$, $y$ consist of $0$ only. Thus $xy^2z = 0^{n+|y|}1^{n+1} \not\in L$. This contradicts the assumption, which means $L$ is not regular.

The general intuition or heuristic here is that any particular regular expression cannot remember count that is arbitrarily large, although it can count to any finite constant.

---

Here is a couple of related exercises, where $\Sigma=\{0,1\}$.

Exercise 1. Is the following language regular? $$ \{w\in \Sigma^* \mid w \text{ has even length and its middle two symbols are 11 or 00}\}. $$

Exercise 2. Is the following language regular? $$ \{w\in \Sigma^* \mid w \text{ has odd length and both of its endpoints are 1} \}. $$