Regular expression over a language - slight confusion [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

Alphabet: Σ = {0, 1}

I'm not too sure what this question is asking. I've posted the answer (just so people don't think it's homework - I'm actually trying to learn these). I'm not quite sure why we have an | in the middle of both of these. I understand that we need Σ for the alphabet, but I'm really confused with what the question is asking. A little confused with 0 in the left and 1 on the right but I believe this is to include the alphabet (0, 1).

Really appreciate all the help.

Edit: This is not a maths question. Also, the answer is from a book in regards to regular expressions but I don't understand how the author got this answer.

Answer 1

The language L₂ is comprised of words with letters denoted w₁ to w_n, where n >= 3 (i.e. words are 3 letters or more) and the second letter (w₂) matches the last letter (w_n).

Given that your alphabet consists of only two letters, you have two possible forms:

1. The second letter is a 0; so the word will start with either character (represented by Σ), followed by a 0, then an unknown number of other characters (Σ* - the asterisk denotes zero or more), and then the final 0.
2. Or the second letter is a 1; so the word will again start with either character (Σ), but then followed by a 1, an unknown number of other characters (Σ*), and the final 1 again.

When you add these two options together and you have: (Σ0Σ*0) + (Σ1Σ*1)