Regular expressions and regular languages

Overview

Recall questions on the metacharacters *, + , ? and |, the difference between ab* and (ab)*, and writing expressions for given sets of strings.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a regular expression?

   Model answer

   A regular expression is simply a way of describing a set — the set of strings that match it. Regular expressions allow particular types of languages to be described in a convenient shorthand notation, far more briefly than by listing the strings, which for most languages would be impossible because the set is infinite.

2. 2

   State the meaning of each of the metacharacters *, +, ? and | in a regular expression, and of grouping parentheses.

   Model answer

   * means 0 or more repetitions of the preceding item. + means 1 or more repetitions. ? means 0 or 1 repetitions, that is the item is optional. | means alternation, that is 'or'. Round brackets ( ) group part of a regular expression so that a following metacharacter applies to the whole group rather than to the last single character.

3. 3

   What set of strings does the regular expression a(a|b)* generate?

   Model answer

   It generates the set of strings that begin with a and are followed by any number of a's and b's in any order, including none at all: {a, aa, ab, aaa, aab, aba, abb, …}. The a at the front is compulsory, the group (a|b) means 'either an a or a b', and the * allows that group to repeat zero or more times.

4. 4

   What is the difference between ab* and (ab)*?

   Model answer

   In ab* the * applies only to the b, so the strings are a, ab, abb, abbb and so on — exactly one a followed by any number of b's. In (ab)* the parentheses group ab so the * applies to the pair, giving the empty string, ab, abab, ababab and so on. The empty string matches (ab)* because * allows zero repetitions, but the shortest string matching ab* is a.

5. 5

   What is the difference between (0|1)* and (0|1)+?

   Model answer

   (0|1)* matches any binary string including the empty string, because * permits zero repetitions. (0|1)+ matches any binary string of at least one character, because + requires one or more repetitions. The only difference between the two sets is whether the empty string belongs.

6. 6

   Write a regular expression that matches both 'color' and 'colour' and nothing else, and explain the metacharacter you used.

   Model answer

   colou?r. The ? applies to the u immediately before it and means 0 or 1 repetitions, so the u is optional: with it you get colour, without it color. No other string matches, because every other character is fixed.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.