Regular expression over the following language

Question

Alphabet E = {a, b, c}

Question and answer: http://d.pr/i/3N41

I understand we must have two a's on the outside but why do we have [] and * - what do these do for this particular expression? In addition to this I'm not quite sure what this means http://d.pr/i/uff7 - { w | |W|} is it just a variable to put the language into?

Any help is greatly appreciated!

Answer 1

To answer the second half of your questions first, that expression can be described as follows:

The language L_a is comprised of the set of words w, where the length of w is a multiple of 3 and w starts with aa.

The vertical bar introduces the conditions that w must meet to be included in the set.

The bars on either side of the second w indicate length.

Then looking at the answer, you have aa, because that's what the word must start with, followed by one other letter (a, b or c), giving you a 3 letter word that's a match.

After that, any other words would need to have an additional 3 letters, each of which can be a, b or c. So the asterisk (*) indicates that this can occur 0 or more times, and the brackets [] just denote which part of the expression the asterisk applies to.

Answer 2

The way I would write this in Bash is aa[abc]([abc][abc][abc])* which means that the token should start with a "aa" followed by 'a' or 'b' or 'c' hence ( aa[abc] )

[abc] is equivalent to (a + b + c) in formal representation means 'a' or 'b' or 'c'

x* means 'x' any number of times, including zero

so ([abc][abc][abc])* means (('a' or 'b' or 'c') three times) occurring any number of times.

the formal way to express that is [(a+b+c)(a+b+c)(a+b+c)]*

the square brackets are like normal parentheses (unlike Bash or Javascript regular expressions for example) but we usually use them when the enclosed portion already has parentheses inside to enhance readability. The asterisk applies to the hole block enclosed in square brackets preceding it.

Answer 3

In this case [...] is grouping three-letter series, and * means 0 or more occurrences.

You have "aa" and then you must have one letter, so that there is (a+b+c) and the rest is optional.