What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

Question

I think it is it 0(01)*(01)*0 U 1(01)*(01)1 where:

• two versions: one that starts and ends with 0, the other that starts and ends with 1
• connected by plus, which does not mean union of both but either or
• repeat of (01)* to make the string even. For example, for 0010 you would

1. start with 0
2. pick 0 from the first 01s
3. pick 0 from the second 01s
4. end with 0

UPDATE: I think this is a more clear and accurate answer: (0+1)(00+11+01+10)∗(0+1)

0+1: You choose either 0 or 1

00 + 11 +01 + 10: All possible options for an even lenght

0+1: last symbol as first

Answer 1

Your original $$\begin{align}&(0(0+1)^\ast(0+1)^\ast0) +\\ &(1(0+1)^\ast(0+1)^\ast1) \end{align}$$ suggestion gets part of the requirements correct: every string begins and ends with the same symbols. But it doesn't get the even-length requirement right, because there is nothing about $(0+1)^\ast(0+1)^\ast$ that forces the two groups to have the same length. The first one could have 7 symbols and the other could have 12, and then the total length would be 19, which you don't want.

Your second suggestion, $$(0+1)(00+11+01+10)^\ast(0+1)$$ gets the length requirement right, but doesn't guarantee that every string has the same beginning and ending symbol, because there is nothing that forces the two $(0+1)$ parts to produce the same symbol. One could be $0$ and the other could be $1$.

You need to combine these two ideas.