HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Regular expression for binary words with 1 in the middle

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressionthewithwordsregularbinaryformiddle

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#104221, answer score: 3

Revisions (0)

No revisions yet.