Search code examples
regular-language

Regular expression over a language - slight confusion

enter image description here

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.

Solution

  • The language L2 is comprised of words with letters denoted w1 to wn, where n >= 3 (i.e. words are 3 letters or more) and the second letter (w2) matches the last letter (wn).

    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)