Regular Expressions

Some basic, informal definitions:

alphabet

a set of symbols (binary alphabet, for example, has symbols 0 & 1)

string

a finite set of symbols from that alphabet

language

a set of strings (made up of symbols from its alphabet)

regular expression (RE)

a way of describing a particular language

More specifically, a regular expression can be

• the empty set or the null string
  
• a single symbol from the alphabet

  for example, if the RE is 0, then the language it describes is a language that consists of exactly one string, the string with the single symbol 0.

• The rest of the definition is built up recursively:

  If r is a regular expression, then so is:

  ( r ) - grouping; you can use parentheses to group parts of REs just as you'd use them in arithmetic expressions

  r * - 0 or more; if the * symbol follows a term of a regular expression, then you can have one or more of that preceding term.

  For example, if the RE is 0 *, then strings in this language are: the null string, 0, 00, 000, 0000, 00000,...

  If r and s are both regular expressions, then so is:

  rs - concatenation.

  For example, if the RE is 0 1 * 0, the strings in the language are: 00, 010, 0110, 01110, 011110, ...

  Another example: if the RE is (10)*, then strings in the language are: the null string, 10, 1010, 101010, 10101010, ...

  r + s - union; strings can be constructing by choosing r or s

  example: if the RE is 0 + 11 + 010 + 000*, then the strings in this language are: 0, 11, 010, 00, 000, 0000, 00000, ...

  another example: if the RE is (00 + 11)*, then strings in this language are: the null string, 00, 11, 0011, 1100, 0000, 1111, 000000, 000011, 001100, 001111, 110000, 110011, 111100, 111111, ...

  ---

  examples

  1. Describe the language defined by this RE: (0* + (10)*)*

  To approach this problem, you can start by listing strings in the language and look for patterns. See whether you can tell if the following strings are in the language:

  1

  01

  10

  00000000

  00100100100

  011011011011

  Do you see any pattern? answer

  2. For each of the examples given, how would you write the corresponding regular expression?

  1. all bit strings that begin with 0 and end with 1
  2. all bit strings whose number of 0's is a multiple of 5
  3. all bit strings with more 1's than 0's
  4. all bit strings with no consecutive 1's

     ANSWERS