Languages and Regular Expressions

Now that we’ve discussed what strings are and how to work with them formally, we’re ready to discuss using them in computations. A typical question we’re going to explore for the first few weeks of this course is how to work with sets of strings that have certain desirable properties. Specifically, we’ll look at simple systematic ways of describing such sets of strings, and we’ll look at simple computation models for recognizing if a string belongs to a particular set.

As examples, we may be interest in

It turns out each of these sets of strings is more difficult to deal with than the previous one!

Let’s get into it. A formal language (or usually just language) is a set of strings over some common alphabet \Sigma. Despite the fancy name, there’s no other structure needed; any set of strings over a single alphabet counts as a language. We use \Sigma^* to denote the language of all strings over \Sigma. Every language over \Sigma is a subset of \Sigma^*, and every subset of \Sigma^* is a language.

Here are some examples of languages:

Languages can be combined and manipulated like any other set (as long as the strings use the same alphabet.) So if we have two languages A and B over some \Sigma, there are also languages:

But there are two more ways to combine languages you should know that are based specifically on them being sets of strings.

The concatenation of languages A and B is denoted as either A \bullet B or AB. It consists of all strings formed by concatenating a string from A with one from B.

A \bullet B := \{x \bullet y \mid \text{$x \in A$ and $y \in B$}\}.

For example, \{\text{SUPER}, \text{SPIDER}, \text{BAT}\} \bullet \{\text{MAN}, \text{WOMAN}\} gives us six superhero names \left\{\begin{gathered} \text{SUPERMAN}, \text{SUPERWOMAN}, \text{SPIDERMAN},\\ \text{SPIDERWOMAN}, \text{BATMAN}, \text{BATWOMAN} \end{gathered}\right\}.

Note that we need an option from both languages to create a string in the concatenation, and concatenation with the empty string results in the same string again, so for any language L \emptyset \bullet L = L \bullet \emptyset = \emptyset and \{\varepsilon\} \bullet L = L \bullet \{\varepsilon\} = L.

The Kleene (“clay-knee”) closure or Kleene star of language L, denoted L^* is the set of strings obtained by concatenating a sequence of zero or more strings from L. In other words, it’s the closure of L over concatenation, the smallest set you can get where the concatenation of its own members is still in the set (but also \varepsilon in case you choose no members for concatenation.) Using more notation, we can say, L^* = \{\varepsilon\} \cup L \cup L \bullet L \cup L \bullet L \bullet L \cup \dots, or L^* is the smallest solution to L^* = \{\varepsilon\} \cup L \bullet L^*, or w \in L^* if and only if

For example, \{0, 11\}^* = \{\varepsilon, 0, 11, 00, 011, 110, 1111, \dots\}.

Notice how the last definition of L^* mirrors the definition of a single string? Well, \Sigma^* is by definition what you would get if you took the Kleene closure over the set of one-symbol strings over \Sigma.

Language L^* always has at least one member, \varepsilon. In particular, \emptyset^* = \{\varepsilon\} = \{\varepsilon\}^*. However, L^* is an infinite set of arbitrarily long (but each individually finite) strings if L contains at least one non-empty string. For example, \{0\}^* = \{\varepsilon, 0, 00, 000, 0000, \dots\}.

Regular languages and regular expressions

It’s often useful, both for practicing the theory and for doing practical programming to be able to describe a language using these operations. In order to do so without writing a ton of sentences describe each language in the recursive construction, we have a concise notation called regular expressions:

Regular expressions are finite, because they represent a finite number of operations to construct a regular language. Also, we can use parentheses to describe the order to do the operations. If it’s not clear by parentheses alone, * has precedence over concatenation, (* immediately after a single symbol means the Kleene closure of the language containing only that symbol,) and concatenation has precedence over +.

For example, \begin{aligned} 0 + 10^* &= \{0\} \cup (\{1\} \bullet \{0\}^*)\\ &= \{0, 1, 10, 100, 1000, \dots\} \end{aligned}

As a word of warning, the regular expressions seen here are not the same as the regexen (singular, regex) you may have seen in some computing environments or programming languages. A regex uses slightly different syntax and supports far more operations on languages than a regular expression, allowing you to describe a more complicated set of languages! Please stick to the notation shown here so that you’re not accidentally creating things that aren’t allowed when we ask for a regular expression.1

It is common to make no distinction between a regular expression and its language even though those are really distinct concepts. More properly, we’d write L(R) to denote the language represented by regular expression R and say string w matches R if w \in L(R). This distinction is like distinguishing between a program and the set of strings it might possibly output.

1

One exception we’ll allow is writing R^{n} for some fixed non-negative integer n to mean the concatenation of exactly n strings from R’s language. For example, (01)^3 is equivalent to (01)(01)(01). We do not want to see + in exponents to mean, “one or more instances of,” because it is too easy to confuse that + for the one that means union. Do not use | to mean union. That’s a regex-only thing. And please please please do not write something like (01)^{2k} to mean an even number of copies of 01. While that language is regular, you’re no longer describing a single regular expression or even something of finite complexity. It’s like you’ve written shorthand for \varepsilon + 01 + 0101 + 010101 + \dots.

Designing regular expressions

There are many interesting regular languages, but in order to prove or take advantage of their regularity (at least for now), you need to be able to design a regular expression that matches the strings in your favorite regular language. Unfortunately, designing regular expressions is less mechanical than say, the induction proofs we were doing for strings; there’s no algorithm for designing regular expressions (or algorithms.) We’ll finish today with some general tips you might find useful and some simple examples employing them.

I don’t personally think of it this way, but Erickson (our “textbook” author and one of the original architects of this course) suggests recognizing regular languages as the output of a somewhat limited programming language. This programming language has no function calls (or goto), it has no unbound variables (meaning you cannot remember what you’ve done in the past), and it makes arbitrary decisions at branch points.

For example, the language of 0 + 10^* would be the output of

if ____:
    print 0
else:
    print 1
    while ____:
        print 0

So to describe a language using a regular expression, you would imagine the simple program used to print any of its strings, and then translate the program back into “regular expression”.

Here’s some other pieces of advice I do employ myself:

Examples

Suppose we want a regular expression to represent the even length binary strings. Any time a character appears, it could be a 0 or a 1; the language for that single symbol is represented by the regular expression 0 + 1. However, the symbols must appear in pairs, and a pair comes from concatenating two of them, represented by (0+1)(0+1). Finally, there can be zero or more of these pairs, represented by ((0+1)(0+1))^*.

Say we want the binary strings of alternating 0s and 1s. In other words, we want the set of binary strings that do not contain the substrings 00 or 11. From the first appearance of 0 (assuming there is one) to the last appearance of 1 (assuming there is one,) we need to repeat the string 01. The repetition can happen zero or more times, so we represent it by having (01)^* appear somewhere in the final expression. Oh, but there may be a 1 proceeding the first 0. Maybe having a 1 means either having an empty string or just the symbol 1, represented by (\varepsilon + 1). The optional 1 and the repetition are together represented by (\varepsilon + 1)(01)^*. Oh, and we may end with a 0 that isn’t followed by a 1. Better go with (\varepsilon + 1)(01)^*(\varepsilon+0) as our final regular expression.

Suppose we want the language of (non-empty) non-negative binary numerals that are divisible by 4 and contain no redundant leading 0s. There exists exactly one valid string with a leading 0 that is not redundant, and it is the string 0 itself. We’ll taking the union (+) of 0 with the regular expression for all the other cases. But at least for those other cases, we are safe to assume there are no leading 0s at all.

No leading 0s (and non-empty) means start with 1. Divisibility by 4 (and being greater than 0) means end with 00. Finally, between that starting 1 and the ending 00 is an arbitrarily long sequence of 0s and 1s given by (0+1)^*. So, the final regular expression (including the lone 0 option) is 0 + 1(0+1)^*00.

There could be multiple valid regular expressions for a language! We call two regular expressions that represent the same language equivalent.

The labs following this lecture are all about building regular expressions for increasingly intricate examples of regular languages. Take advantage of this opportunity to get used to them as a group before we throw much harder examples at you in the homework!