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?

New contributor
Dalton is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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

Dalton is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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