Just as finite automata are used to recognize patterns of strings, regular expressions are used to generate patterns of strings. A regular expression is an algebraic formula whose value is a pattern consisting of a set of strings, called the language of the expression.
Operands in a regular expression can be:
Operators used in regular expressions include:
L(R1|R2) = L(R1) U L(R2).
L(R1R2) = L(R1) concatenated with L(R2).
L(R1*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...
Closure has the highest precedence, followed by concatenation, followed by union.
The set of strings over {0,1} that end in 3 consecutive 1's.
(0 | 1)* 111
The set of strings over {0,1} that have at least one 1.
0* 1 (0 | 1)*
The set of strings over {0,1} that have at most one 1.
0* | 0* 1 0*
The set of strings over {A..Z,a..z} that contain the word "main".
Let <letter> = A | B | ... | Z | a | b | ... | z <letter>* main <letter>*The set of strings over {A..Z,a..z} that contain 3 x's.
<letter>* x <letter>* x <letter>* x <letter>*
The set of identifiers in Pascal.
Let <letter> = A | B | ... | Z | a | b | ... | z Let <digit> = 0 | 1 | 2 | 3 ... | 9 <letter> (<letter> | <digit>)*
The set of real numbers in Pascal.
Let <digit> = 0 | 1 | 2 | 3 ... | 9 Let <exp> = 'E' <sign> <digit> <digit>* | epsilon Let <sign> = '+' | '-' | epsilon Let <decimal> = '.' <digit> <digit>* | epsilon <digit> <digit>* <decimal> <exp>
Regular expressions are used frequently in Unix:
To facilitate construction of regular expressions, Unix recognizes additional operators. These operators can be defined in terms of the operators given above; they represent a notational convenience only.
Regular expressions and finite automata have equivalent expressive power:
The proof is in two parts:
Our construction of FA from regular expressions will allow "epsilon transitions" (a transition from one state to another with epsilon as the label). Such a transition is always possible, since epsilon (or the empty string) can be said to exist between any two input symbols. We can show that such epsilon transitions are a notational convenience; for every FA with epsilon transitions there is a corresponding FA without them.
We begin by showing how to construct an FA for the operands in a regular expression.
Given FA for R1 and R2, we now show how to build an FA for R1R2, R1|R2, and R1*. Let A (with start state a0 and final state aF) be the machine accepting L(R1) and B (with start state b0 and final state bF) be the machine accepting L(R2).
If we can eliminate epsilon transitions from an FA, then our construction of an FA from a regular expression (which yields an FA with epsilon transitions) can be completed.
Observe that epsilon transitions are similar to nondeterminism in that they offer a choice: an epsilon transition allows us to stay in a state or move to a new state, regardless of the input symbol.
If starting in state s1, we can reach state s2 via a series of epsilon transitions followed by a transition on input symbol x, we can replace all of the epsilon transitions with a single transition from s1 to s2 on symbol x.
To construct a regular expression from a DFA (and thereby complete the proof that regular expressions and finite automata have the same expressive power), we replace each state in the DFA one by one with a corresponding regular expression.
Just as we built a small FA for each operator and operand in a regular expression, we will now build a small regular expression for each state in the DFA.
The basic idea is to eliminate the states of the FA one by one, replacing each state with a regular expression that generates the portion of the input string that labels the transitions into and out of the state being eliminated.
Given a DFA F we construct a regular expression R such that
L(F) == L(R).
We preprocess the FA, turning the labels on transitions into regular expressions. If there is a transition with label {a,b}, then we replace the label with the regular expression a | b. If there is no transition from a state to itself, we can add one with the label NULL.
For each accepting state sF in F, eliminate all states in F except the start state s0 and sF.
To eliminate a state sE, consider all pairs of states sA and sB such that there is a transition from sA to sE with label R1, a transition from sE to sE with label R2 (possibly null, meaning no transition), and a transition from sE to sB with label R3. Introduce a transition from sA to sB with label R1R2*R3. If there is already a transition from sA to sB with label R4, then replace that label with R4|R1R2*R3.
After eliminating all states except s0 and sF:
Let RFi be the regular expression produced by eliminating all the states except s0 and sFi. If there are n final states in the DFA, then the regular expression that generates the strings accepted by the original DFA is RF1 | RF2 | ... RFn.
We have shown that all four of the following formalisms for expressing languages of strings are equivalent: