How to write a regular expression to match a string that starts with the same pattern that it ends with

Question

Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with.

Let's say that we have an alphabet composed of the binary symbols: {0,1}

We should make a regular expression to create a language that is composed of words (W) with the following pattern:

W=w1w2w1 and w1 and w2 are words from the closure of the {0,1} alphabet.

I do not know how to approach this task. I am not convinced it is even possible because there is no way we can memorize anything inside a regex.

The only operators that we should use are the following three: -Concatenation -Star (closure) -OR

Answer 1

Since you asked how to approach it, a good starting point for these sorts of problems is to start by understanding the language. Try writing down all words in the language of length 1; all words of length 2; all words of length 3; all words of length 4; and see if you can spot any possible patterns (about which words are in the language and which aren't). Then, see if you can prove your guess.

Finally, use that to help you brainstorm ideas for how to express this as a regular expression.

Make sure to read How to prove a language is regular? carefully.