3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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} \}. $$

$\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.