Regular Expression VS Finite Automata

Question

I am having a hard time to follow a concept from Introduction to the theory of computation (3rd ed.) by Michael Sipser. I got confused by the last sentence. Ok, we can convert regular express into finite automata and vice versa. Does "Recall that a regular language is one that is recognized by some finite automaton." mean we can use more than one finite automata to describe one singular regular expression? if so, can we use more than one regular expresses to describe one singular finite automaton? If not, what does the last sentence really mean?

Content from the book On page 66

Regular expressions and finite automata are equivalent in their descriptive power. This fact is surprising because finite automata and regular expressions superficially appear to be rather different. However, any regular expression can be converted into a finite automaton that recognizes the language it describes, and vice versa. Recall that a regular language is one that is recognized by some finite automaton.

Answer 1

Kleene's Theorem for Regular Languages provides the equivalence of regular expressions and finite state machines. The definition of a regular language is as follows:

Let $\Sigma$ be an alphabet. The following are precisely the regular languages over $\Sigma$:

• $L = \emptyset$
• $L = \{a\}$ (for some $a \in \Sigma$
• If $L_{1}, L_{2}$ are regular, then $L_{1} \cup L_{2}, L_{1} \cdot L_{2}$ (the concatenation of $L_{1}$ with $L_{2}$), and $L_{1}^{*}$ are regular.

These are the only regular languages over $\Sigma$.

Note that the above definition provides the basic syntax for regular expressions. Now Kleene's Theorem states that $L$ is regular if and only if $L$ is accepted by some DFA. This proof is enormous, and really provides the content for about 2/3-3/4 of the regular languages unit in a Theory of Computation course.

The forward direction of the proof (if $L$ is regular, then $L$ is accepted by some DFA) provides some of useful procedures, including:

• Thompson's Construction Algorithm to convert a regular expresion to an $\epsilon$-NFA

• The subset construction procedure to convert ($\epsilon$)-NFAs to DFAs

The converse direction also requires some procedures, primarily to convert a DFA to a regular expression. The state reduction procedure is the standard procedure for classes like this. Brzozowski's Algebraic Method is another (and a personal preference).

To sum it up:

• Given a regular expression $R$ generating the language $L$, we can construct a DFA $D$ from $R$ that accepts $L$. There may exist other DFAs that also accept $L$.

• Given a DFA $D$, we can construct a regular expression $R$ such that $R$ generates $L(D)$. There may be other regular expressions that generate $L(D)$.

Answer 2

A finite automata accepts just one regular language and that language is the set of words that, when put into the automata, lead to an accepting state.

On the other hand, there is more than one automaton accepting a given language. For example, let $\Sigma = \{0,1\}$ be the alphabet and $L = \{\varnothing, 0, 00, 000, \dots\}$ be the regular language. Then $L$ is accepted by both

and