More examples

Ex. 5:
Describe as simply as possible in English the language corresponding to the regular expression (( a + b )3)*( #+ a + b ) .

Solution:
(( a + b )3) represents the strings of length 3. Hence (( a + b )3)* represents the strings of length a multiple of 3. Since (( a + b )3)*( a + b ) represents the strings of length 3n + 1, where n is a natural number, the given regular expression represents the strings of length 3n and 3n + 1, where n is a natural number.

Examples of Regular Expressions and Regular Languages.

examples of Regular expressions and Regular Languages.
Ex.:
Let r1 and r2 be arbitrary regular expressions over some alphabet. Find a simple (the shortest and with the smallest nesting of * and +) regular expression which is equal to each of the following regular expressions.

(a) (r1 + r2 + r1r2 + r2r1)*
(b) (r1(r1 + r2)*)+

Solution:
One general strategy to approach this type of question is to try to see whether or not they are equal to simple regular expressions that are familiar to us such as a, a*, a+, (a + b)*, (a + b)+ etc.

(a) Since (r1 + r2)* represents all strings consisting of strings of r1 and/or r2 , r1r2 + r2r1 in the given regular expression is redundant, that is, they do not produce any strings that are not represented by (r1 + r2)*. Thus (r1 + r2 + r1r2 + r2r1)* is reduced to (r1 + r2)*.

(b) (r1(r1 + r2)*)+ means that all the strings represented by it must consist of one or more strings of (r1(r1 + r2)*). However, the strings of (r1(r1 + r2)*) start with a string of r1 followed by any number of strings taken arbitrarily from r1 and/or r2.
Thus anything that comes after the first r1 in (r1(r1 + r2)*)+ is represented by (r1 + r2)*. Hence (r1(r1 + r2)*) also represents the strings of (r1(r1 + r2)*)+, and conversely (r1(r1 + r2)*)+ represents the strings represented by (r1(r1 + r2)*). Hence (r1(r1 + r2)*)+ is reduced to (r1(r1 + r2)*).

In our next Posts, we will see some more good examples of Regular expressions and Regular Languages.