patternMinor
Regular expression for binary words with 1 in the middle
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?
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.