Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Regular expressions are used to describe languages, in this article we discuss regular expressions and show that every language can be described by a regular expression.

### Table of contents.

- Introduction.
- Regular Expressions.
- Equivalence of regular expressions and regular languages.
- Summary.
- References.

### Prerequisites.

## Introduction.

*Regular expressions* are a means to describe languages, they define a finite pattern of *strings* or *symbols*.

Each pattern will match a set of strings and therefore they serve as names for a set of strings.

## Regular Expressions.

To get a idea about what regular expressions involve, let's go through a few examples:

*Example 1:*

Consider the expression *(0 âˆª 1)01**.

The language that is described by the above expression is the set of all binary strings,

- that start with
*0*or*1*as indicated by*0 âˆª 1*, - for which the second symbol is
*0*, - that end with zero or more
*1s*as indicated by*1**.

A sample language is such as the following;

*{00, 001, 0011, 00111, ..., 10, 101, 1011, 10111, ...}*

*Example 2:*

The expression *1*01*01** defines the language:

*{w : w contains exactly two 0s}*

*Example 3:* The expression *1011 âˆª 0* describes the language *{1011, 0}*.

*Example 4:* The expression *((0 âˆª 1)(0 âˆª 1))** describes the language *{w : the length of w is even}*

*Example 5:* The expression *(0 âˆª 1)*1011(0 âˆª 1)** describes the language *{w : 1011 is a substring of w}*

*Example 6:* The expression *(0 âˆª 1)*0(0 âˆª 1)*0(0 âˆª 1)** describes the language *{w : w contains at least two 0s}*

**Definition 1:** Let Î£ be a non-empty alphabet.

*Ïµ*is a regular expression.*âˆ…*is a regular expression.- For each
*a âˆˆ Î£*,*a*is a regular expression. - If
*R1*and*R2*are regular expressions, then*R1 âˆª R2*is also a regular expression. - If
*R1*and*R2*are regular expressions, then*R1R2*is also a regular expression. - If
*R*, then*R**is also a regular expression.

From the above listing, *1-3* are regarded as the building blocks of regular expressions while *3-6* define rules used to combine regular expressions into new/larger regular expressions.

*An example:* We claim that *(0 âˆª 1)*101(0 âˆª 1)** is a regular expression where the alphabet Î£ is {0, 1}.

**Proof:** We have to show that the expression can be built using the rules defined above.

- By rule
*3*,*0*and*1*are regular expressions. - By rule
*4*,*0 âˆª 1*is a regular expression since both*0*and*1*are regular expressions. - By rule
*5*,*10*and*101*are both regular expressions. - By rule
*5*,*(0 âˆª 1)*101*is a regular expression since*(0âˆª1)**and*101*are also regular expressions. - By rule
*5*,*(0 âˆª 1)*101(0 âˆª 1)**is a regular expression since*(0âˆª1)*101*and*(0âˆª1)**are both regular expressions. - By rule
*6*,*(0 âˆª 1)**is a regular expression.

Now we define the language that is described by the above regular expressions.

*Ïµ*describes the language*{Ïµ}*.*âˆ…*describes the language*{âˆ…}*.- For each
*a âˆˆ Î£*,*a*describes the language*{a}*. - Let
*R1*and*R2*be regular expressions and*L1*and*L2*be the languages described by these expressions respectively. The regular expressions*R1 âˆª R2*describes the language*L1 âˆª L2*. - Also assume the above for the languages
*L1*and*L2*and the expressions*R1*and*R2*, The regular expression*R1R2*also describes the language*L1L2*. - Let
*R*be a regular expression and*L*be the language described by it. The regular expression*R**describes the language*L**.

*Example 1:*

Regular expression *0 âˆª Ïµ* describes the language *{0, Ïµ}* whereas the expression *1** describes the language *{Ïµ, 1, 11, 111, ..., }* and therefore, the regular expression *(0 âˆª Ïµ)1** describes the language *{0, 01, 011, 0111, ..., Ïµ, 1, 11, 111, ...}*.

*Example 2:* Regular expression *(0 âˆª Ïµ)(1 âˆª Ïµ)* describes the language *{01, 0, 1, Ïµ}*.

**Definition 2:** Let *R1* and *R2* be regular expressions and *L1* and *L2* be languages described by the expressions, then if *L1* = *L2*, that is, *R1* and *R1* describe the same language, then we can write *R1* = *R2*.

Therefore, even if *(0 âˆª Ïµ)1** and *01** âˆª *1** are different regular expressions, we can write,

*(0 âˆª Ïµ)1* = 01* âˆª 1**

because they describe the same language.

**Theorem:** Let *R1*, *R2*, *R3* be regular expressions. The following identities hold.

- R1âˆ… = âˆ…R1 = âˆ….
- R1Ïµ = ÏµR1 = R1.
- R1 âˆª âˆ… = âˆ… âˆª R1 = R1.
- R1 âˆª R1 = R1.
- R1 âˆª R2 = R2 âˆª R1.
- R1(R2 âˆª R3) = R1R2 âˆª R1R3.
- (R1 âˆª R2)R3 = R1R3 âˆª R2R3.
- R1(R2R3) = (R1R2)R3.
- âˆ…* = Ïµ.
- Ïµ* = Ïµ.
- (Ïµ âˆª R1)* = R1*.
- (Ïµ âˆª R1)(Ïµ âˆª R1)* = R1*.
- R1*(Ïµ âˆª R1) = (Ïµ âˆª R1)R1*=R1*.
- R1*R2 âˆª R2 = R1*R2.
- R1(R2R1)* = (R1R2)*R1.
- (R1 âˆª R2)*= (R1*R2)*R1* = (R2*R1)*R2*.

We shall not present proof for the above identities however we assume they are verified.

*For example:* We can verify the identity *(0 âˆª Ïµ)1* = 01* âˆª 1** as follows,

- By identity
*7*: (0 âˆª Ïµ)1* = 01* âˆª Ïµ1* - By identity
*2*: (0 âˆª Ïµ)1* = 01* âˆª 1*

## Equivalence of regular expressions and regular languages.

**Theorem:** Let *L* be a language, then *L* is regular iff there exists a regular expression describing *L*.

The proof of this theorem entails two parts:

- First we will prove that every regular expression describes a regular language.
- Second, we prove that every DFA
*M*can be converted to a regular expression describing a language*L(M)*.

## 1. Every regular expression describes a regular language

Let *R* be an arbitrary regular expression over the alphabet Î£.

We need to prove that the language that is described by *R* is a regular language.

We prove using induction on the structure of *R*, that is, by induction on the way *R* is built using the rules we defined earlier(definition 1).

**Base case 1:** Assuming *R = Ïµ*, then *R* describes the language *{Ïµ}* and to prove that it is regular we shall construct a NFA *M = (Q,Î£, Î´, q, F)* that accepts this language.

We obtain this *NFA* by defining

*Q = {q}*, *q* the start state, *F = {q}* and *Î´(q, a) = âˆ…* for all a âˆˆ Î£Ïµ

State diagram of *M*:

**Base case 2:** Assuming *R = âˆ…*, then *R* describes the language âˆ… and to prove that it is regular, we construct an NFA *M = (Q,Î£, Î´, q, F)* that accepts it. We obtain this *NFA* by defining *Q = {q}*, *q* the start state, *F = âˆ…*, and *Î´(q, a) = âˆ…* for all *a âˆˆ Î£Ïµ*.

The state diagram of *M*:

**Base case 3:** Let *a âˆˆ Î£*, assume *R = a*, then *R* describes the language *{a}* and to prove that it is regular we construct a NFA *M= (Q,Î£, Î´, q1, F)* that accepts it. The *NFA* is obtained by defining *Q = {q1, q2}*, *q1* is the start state, *F = {q2}*, and

*Î´(q1, a) = {q2}*,

*Î´(q1, b)* = *âˆ… for all b âˆˆ Î£Ïµ \ {a}*,

*Î´(q2, b)* = *âˆ… for all b âˆˆ Î£Ïµ*.

State diagram of *M* is shown below.

**Induction step 1 of base case 1:** Assuming *R = R1 âˆª R2* where *R1* and *R2* are regular expressions. Let *L1* and *L2* be regular languages described by *R1* and *R2* respectively, then *R* describes the language *L1 âˆª L2* which is also regular by *Theorem 1.1* in the prerequisite article.

**Induction step of base case 2:** Assuming that *R = R1R2* where *R1* and *R2* are regular expressions. Let *L1* and *L2* be two regular languages described by the regular expressions respectively, then *R* describes the language *L1L2* which by *Theorem 4* in the prerequisite article is regular.

**Induction step of base case 3:** Assuming that *R = (R1)** where *R1* is regular expression. Let *L1* be the language described by *R1* and assuming that *L1* is regular, then *R* describes the language *(L1)** which by *Theorem 5* in the prerequisite article is regular.

At this point we conclude the proof of the claim that *every regular expression describes a regular language*.

*An example:*

Consider the regular expression: *(ab âˆª a)**, where *{a, b}* is the alphabet. We construct a *NFA* that accepts the language described by the regular expression to prove that the regular expression describes a regular language.

Lets first build a regular expression:

- First we take the regular expressions
*a*and*b*and combine them to a regular expression*ab*. - Next, we take the regular expressions
*ab*and*a*and combine them into regular expression*ab âˆª a*. - We take regular expression
*ab âˆª a*and transform it into the regular expression*(ab âˆª a)**.

Now to construct an *NFA*:

- We construct
*NFA M1*that accepts the language described by regular expression*a*:

- We construct
*NFA M2*that accepts the language described by regular expression*b*:

- Apply the construction from the proof of
*Theorem 4(prerequisite article)*to*M1*and*M2*which gives*NFA M3*that accepts the language described by the regular expression*ab*:

- Apply the construction from proof of
*Theorem 1.1:(prerequisite article)*to*M1*and*M3*which gives*NFA M4*that accepts the language described by regular expression*ab âˆª a*:

- Apply construction from proof of
*Theorem 5(prerequisite article)*to*M4*which gives*NFA M5*that accepts language described by regular expression*(ab âˆª a)**

## 2. Converting a DFA to a regular expression.

We will prove that every *DFA M* can be converted into a regular expression describing a language *L(M)*.

First we solve recurrence relations involving languages.

**Solving recurrence relations.**

Let *Î£* be an alphabet, *B* and *C* be known languages in *Î£** such that *Ïµ âˆ‰ B* and *L* be an unknown language such that *L = BL âˆª C*.

Let's try to express *L* in terms of *B* and *C* hence solving it.

To start consider an arbitrary string *u* in language *L*. Now to determine how *u* looks like. Since *u âˆˆ L* and *L = BL âˆª C*, we know *u* is a string in *BL âˆª C* and therefore we have the following possibilities:

*u*is an element of*C*.*u*is an element of*BL*, if this is the case, then there are strings*b âˆˆ B*and*v âˆˆ L*such that*u = bv*. Since*Ïµ âˆ‰ B*, we have*b â‰ Ïµ*and thus,*|v| < |u|*. Since*v*is a string in*L*which is equal to*BL âˆª C*,*v*is a string in*BL âˆª C*and we have the following possibilities for*v*.

*v*is an element of*C*, if this is the case,*u = bv*where*b âˆˆ B*and*v âˆˆ C*and therefore*u âˆˆ BC*.*v*is an element of*BL*, if this is the case, there are strings*bâ€² âˆˆ B*and*w âˆˆ L*such that*v = bâ€² w*. Since*Ïµ âˆ‰ B*we have*bâ€² â‰ Ïµ*, therefore,*|w|*<*|v|*. Since*w*is a string in*L*, there are two further possibilities.

***w*is an element of*C*, if this is the case,*u = bbâ€² w*, where*b*,*bbâ€² âˆˆ B*and*w âˆˆ C*, therefore*u âˆˆ BBC*.

***w*is an element of*BL*, if this is the case, there are strings*bâ€²â€² âˆˆ B*and*x âˆˆ L*such that*w = bâ€²â€²x*. Since*â‰ Ïµ B*we have*bâ€²â€² â‰ Ïµ*and therefore *|x| < |w|. Since*x*is a string in*L*,*x*is also a string in*BL âˆª C*and we have another two further possibilities for*x*.

****x*is an element in*C*, if this is the case,*u = bbâ€² bâ€²â€² x*where*b, bâ€², bâ€²â€² âˆˆ B*and*x âˆˆ C*and therefore*u âˆˆ BBBC*.

****x*is an element of*BL*and so on...

From the above we are convinced that any string *u* in *L* can be written as a concatenation of zero or more strings in *B* followed by one string in *C*.

**Lemma 1:** Let *Î£* be an alphabet and *B*, *C*, *L*, be languages in *Î£** such that *Ïµ â‰ B* and *L = BL âˆª C*, then *L = B*C*.

**Proof:**

We first show that *B*C âŠ† L*. Let *u* be an arbitrary string *B*C*. Then *u* is the concatenation of *k* strings of *B* for some *k â‰¥ 0* followed by one string of *C*.

*The base case*: k = 0, *u* is a string in *C*, therefore *u* is a string in *BL âˆª C*. Since *L = BL âˆª C*, *u* is a string in L.

*Inductive step:* *k â‰¥ 1*, we write *u = vwc* where *v* is a string in *B*, *w* is the concatenation of *k-1* strings of *B* and *c* is a string of *C*.

We define *y = wc* and observe that *y* is the concatenation of *k-1* strings of *B* followed by a single string of *C*.

By induction, string *y* is an element of *L*, therefore *u = vy* where *v* is a string in *B* and *y* a string in *L*.

This shows that *u* is a string in *BL* and therefore *u* is a string in *BL âˆª C* and since *L = BL âˆª C* if follows that *u* is a string in *L*.

We have completed the proof that *B*C âŠ† L*.

To show that *L âŠ† B*C*, let *u* be an arbitrary string in *L* and *l* its length. By induction we will prove that *u* is a string in *B*C*.

*Base case:* *l = 0*, *u = Ïµ* and since *u âˆˆ L* and *L = BL âˆª C*, *u* is a string in *BL âˆª C*. Since *Ïµ â‰ B*, *u* cannot be a string in *BL* and hence *u* must be a string in *C*.

Since *C âŠ† B*C*, *u* is a string in *B*C*.

*Induction step:* *l â‰¥ 1*, If *u* is a string in C, *u* is a string in *B*C* and we are done.

Assuming *u* is not a string in *C*. Since *u âˆˆ L* and *L = BL âˆª C*, *u* is a string in *BL*. Therefore there are strings *b âˆˆ B* and *v âˆˆ L* such that *u = bv*.

Since *Ïµ â‰ B*, the length of *b* is greater or equal to 1 and therefore the length of *v* is less than the length of *u*.

By induction, *v* is a string in *B*C* and hence *u = bv* where *b âˆˆ B* and *v âˆˆ B*C* which shows *u âˆˆ B(B*C)*. Since *B(B*C) âŠ† B*C*, it shows that *u âˆˆ B*C*.

This lemma holds for any language *B* that doesn't contains an empty string *Ïµ*.

**Converting DFA to regular expression.**

We use lemma 1 to prove that every DFA can be converted to a regular expression.

Let *M = (Q,Î£, Î´, q, F)* be an arbitrary deterministic finite automaton.

We will show that there exists a regular expression that describes a language *L(M)*.

For each state *r âˆˆ Q* we define:

*Lr={w âˆˆ Î£*: the path in the state diagram of M that starts in state r and corresponds to w ends in state F}.* That is, *Lr* is the language accepted by *M* , if *r* was the start state.

Now we show that *Lr* can be described by a regular expression, Since *L(M) = Lq*, it proves that *L(M)* can be described by a regular expression.

The idea is to set up equations for the languages *Lr* which we then solve using lemma 1.

We claim that

*${\mathrm{L}}_{\mathrm{r}}=\underset{\mathrm{a}\xe2\u02c6\u02c6\mathrm{\xce\pounds}}{\overset{}{\xe2\u2039\u0192}}\mathrm{a}.{\mathrm{L}}_{\mathrm{\xce\xb4}(\mathrm{r},\mathrm{a})\xc2}\xc2\mathrm{if}\xc2\mathrm{r}\xe2\u02c6\u2030\mathrm{F}$*

Let *w* be a string *Lr*, then the path *P* in the state diagram of *M* starting in state *r* and corresponding to *w* ends in state *F*.

Since *r âˆ‰ F*, this path contains at least one edge.

Let *râ€²* be the following state after the first state, then *râ€² = Î´(r, b)* for some symbol *b âˆˆ Î£*.

Therefore, *b* is the first symbol of *w*.

We write *w = bv* where *v* is the remaining part of *w*.

Then the path *Pâ€² = P \ {r}* in the state diagram *M* starting in state *râ€²* and corresponding to *v* ends in state *F*.

Thus, *v âˆˆ Lrâ€² = LÎ´(r, b)*.

Hence:

*$\mathrm{w}\xe2\u02c6\u02c6\mathrm{b}.{\mathrm{L}}_{\mathrm{\xce\xb4}\left(\mathrm{r},\mathrm{b}\right)\xc2}\xe2\u0160\u2020\underset{\mathrm{a}\xe2\u02c6\u02c6\mathrm{\xce\pounds}}{\overset{}{\xe2\u2039\u0192}}\mathrm{a}.{\mathrm{L}}_{\mathrm{\xce\xb4}\left(\mathrm{r},\mathrm{a}\right)\xc2}\xc2$*

Conversely, let *w* be a string in *${\xe2\u2039\u0192}_{\mathrm{a}\xe2\u02c6\u02c6\mathrm{\xce\pounds}}^{}\mathrm{a}.{\mathrm{L}}_{\mathrm{\xce\xb4}\left(\mathrm{r},\mathrm{a}\right)\xc2}$*, then there is a symbol *b âˆˆ Î£* and a string *v âˆˆ ${\mathrm{L}}_{\mathrm{\xce\xb4}\left(\mathrm{r},\mathrm{b}\right)\xc2}$* such that *w = bv*.

Let *Pâ€²* be a path in the state diagram of *M* starting in state *Î´(r, b)* and corresponding to *v*.

Since *v âˆˆ ${\mathrm{L}}_{\mathrm{\xce\xb4}\left(\mathrm{r},\mathrm{b}\right)\xc2}$*, this path ends in a state *F*.

Let *P* be the path in the state diagram of *M* starting in *r* and follows the edge to *Î´(r, b)*, then follows *Pâ€²*.

This path corresponds to *w* and end in a state *F* and therefore *w âˆˆ Lr*.

We complete the proof of the claim.

In a similar fashion we can prove that:

*${\mathrm{L}}_{\mathrm{r}}=\mathrm{\xcf\mu}\xe2\u02c6\xaa(\underset{\mathrm{a}\xe2\u02c6\u02c6\mathrm{\xce\pounds}}{\overset{}{\xe2\u2039\u0192}}\mathrm{a}.{\mathrm{L}}_{\mathrm{\xce\xb4}(\mathrm{r},\mathrm{a})\xc2})\xc2\mathrm{if}\xc2\mathrm{r}\xe2\u02c6\u2030\mathrm{F}$*

In this case we have a set of equations in the *unknowns* *Lr* for *r âˆˆ Q*.

The total number of equations is equal to the number of unknowns(size of *Q*).

To obtain the regular expression of *L(M) = Lq)* we solve the equations using lemma 1, for this we have to convince ourselves that these equations have a solution for any *DFA*.

**Lemma 2:** Let *n â‰¥ 1* be an integer and for *1 â‰¤ i â‰¤ n* and *1 â‰¤ j â‰¤ n*, let *${\mathrm{B}}_{\mathrm{ij}}$* and *${\mathrm{C}}_{\mathrm{i}}$* be regular expressions such that *Ïµ â‰ ${\mathrm{B}}_{\mathrm{ij}}$*. Let *L1, L2, ..., Ln* be languages satisfying:

*${\mathrm{L}}_{\mathrm{i}}=\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{ij}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{i}}\xc2\mathrm{for}\xc21\xe2\u2030\xa4\mathrm{i}\xe2\u2030\xa4\mathrm{n}$*

Then *L1* is expressed as a regular expression by involving regular expressions *${\mathrm{B}}_{\mathrm{ij}}$ and ${\mathrm{C}}_{\mathrm{i}}$*.

**Proof:** We prove this lemma by an induction on *n*.

*Base case:* n = 1, therefore, we have

*L1 = ${\mathrm{B}}_{\mathrm{11}}$ ${\mathrm{L}}_{1}$ âˆª ${\mathrm{C}}_{1}$*

Since *Ïµ âˆ‰ ${\mathrm{B}}_{\mathrm{11}}$*, by lemma 1 that *L1 = ${{\mathrm{B}}^{*}}_{11}$${\mathrm{C}}_{\mathrm{1}}$*, this proves the base case.

*Induction step:* Let *n â‰¥ 2*, we assume that the lemma is true for *n-1*, we have:

*${\mathrm{L}}_{\mathrm{n}}=\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{nj}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{n}}$*

= *${\mathrm{B}}_{\mathrm{nn}}{\mathrm{L}}_{\mathrm{n}}\xe2\u02c6\xaa\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{nj}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{n}}$*

Since *Ïµ âˆ‰ ${\mathrm{B}}_{\mathrm{nn}}$*, then from lemma 1:

*${\mathrm{L}}_{\mathrm{n}}={\mathrm{B}}_{\mathrm{nn}}^{*}\left(\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{nj}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{n}}\right)$*

= *${\mathrm{B}}_{\mathrm{nn}}^{*}\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{nj}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{C}}_{\mathrm{n}}$*

= *$\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{B}}_{\mathrm{nj}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{C}}_{\mathrm{n}}$*

By substituting the equation for *Ln*, into equations for *Li*, *1 â‰¤ i â‰¤ n âˆ’ 1* we obtain the equation.

*${\mathrm{L}}_{\mathrm{i}}=\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{ij}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{i}}$*

= *${\mathrm{B}}_{\mathrm{in}}{\mathrm{L}}_{\mathrm{n}}\xe2\u02c6\xaa\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}{\mathrm{B}}_{\mathrm{ij}}{\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{i}}$*

= *$\left(\underset{\mathrm{j}=1}{\overset{\mathrm{n}-1}{\xe2\u2039\u0192}}({\mathrm{B}}_{\mathrm{in}}{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{B}}_{\mathrm{nj}}\xe2\u02c6\xaa{\mathrm{B}}_{\mathrm{ij}}){\mathrm{L}}_{\mathrm{j}}\right)\xe2\u02c6\xaa{\mathrm{B}}_{\mathrm{in}}{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{C}}_{\mathrm{n}}\xe2\u02c6\xaa{\mathrm{C}}_{\mathrm{i}}$*

An therefore we have *n-1* equations in *L1, L2,...,Ln-1* and since *$\mathrm{\xcf\mu}\xe2\u02c6\u2030{\mathrm{B}}_{\mathrm{in}}{\mathrm{B}}_{\mathrm{nn}}^{*}{\mathrm{B}}_{\mathrm{nj}}\xe2\u02c6\xaa{\mathrm{B}}_{\mathrm{ij}}$*, it follows from the induction hypothesis that *L1* can be expressed as a regular expression only involving the regular expressions *${\mathrm{B}}_{\mathrm{ij}}$ and ${\mathrm{C}}_{\mathrm{i}}$*

## Summary.

Regular expressions are a means to describe languages, in this article, we proved that every regular expression describes a regular language and that every DFA can be converted to a regular expression that describes a language.