3.1.2 Examples of Regular Expressions

Introduction of regular Expressions.

But what are regular expressions? Here are four examples:

The building stones of regular expressions are symbols. These symbols can then be connected in a number of ways to represent sets of strings. Before we go into the details, let's look more closely at the above examples. and are regular expressions representing the singleton sets of strings and . They correspond to the following automata:

Regular expressions can be concatenated. The regular expression represents the (also singleton) set of strings . It should be clear what the corresponding automaton looks like. We can furthermore combine regular expressions by disjunction. The regular expression represents the set of strings and corresponds to this automaton:

Finally, is the set of all strings that consist of as and bs in any order. The empty word is also accepted. The automaton looks as follows:

From the examples you might already have guessed that there is a systematic way of translating regular expressions into finite state automata, which means that we never actually have to specify automata - we only have to write regular expressions.