13 \mathbf{Regular} – the set of all regular languages

In this chapter we collect sistematically some results we saw in previous chapters (Chapter 9 and Chapter 12): make sure you have already read them!

We saw that there are three different ways to describe some languages:

using regular expressions (see Chapter 12),
using DFAs (Section 9.2), and
using \varepsilon-NFAs (Section 9.1).

In particular, we proved theorems that showed the equivalence of the three models. We collect such results in Theorem 13.1 below.

Theorem 13.1 Let L\subseteq \Sigma^*. The following are equivalent:

there exists a regular expression r over \Sigma s.t. \mathscr{L}(r)=L.
there exists a DFA A s.t. \mathscr{L}(A)=L.
there exists an \varepsilon-NFA B s.t. \mathscr{L}(B)=L.

Proof [See if you can fill in the details yourself (before looking at the proof).]

Its proof is just collecting results seen so far.

The implication (1)\implies (3) follows easily from the NFAs you constructed in Exercise 9.1 and Exercise 9.4.
The implication (3)\implies (2) is Theorem 9.2.
The implication (2)\implies (1) is Theorem 12.1.

Exercise 13.1 Prove the implication (1)\implies (3) of Theorem 13.1.

The previous theorem justifies the following definition.

Definition 13.1 (regular language) A language L\subseteq \Sigma^* is regular if any of the conditions in Theorem 13.1 hold. \mathbf{Regular} is the set of all regular languages.

In particular, to show that a language L is regular you don’t need to construct a DFA! You have the freedom of constructing a \varepsilon-NFA or a regular expression!

Exercise 13.2 Show¹ that \mathbf{Finite}\cup \mathbf{co}\mathbf{Finite}\subsetneq\mathbf{Regular}.

Exercise 13.3 The set of all languages over \Sigma^* (that is \mathscr{P}(\Sigma^*)) has the following properties

it contains \emptyset;
it contains \{\varepsilon\};
it contains \{\textcolor{darkred}{\mathtt{s}}\} for each symbol \textcolor{darkred}{\mathtt{s}}\in \Sigma;
it is closed under union;
it is closed under concatenation;
is is closed under Kleene star

Show² that \mathbf{Regular} is the smallest (w.r.t. inclusion) set of languages with the properties above, that is show that

\mathbf{Regular} has the properties above, and
every class of languages with the properties above contains \mathbf{Regular}.

Exercise 13.4 Show that for every alphabet \Sigma, the set of all regular languages over \Sigma is countable. As a consequence of this, also show that there must exist uncountably many languages L\subseteq \Sigma^* that are not in \mathbf{Regular}.³

Exercise 13.5 Given the description of a regular language as a regex/DFA/NFA, what is the cost of (a reasonable) algorithm that produces a description of the same language but with one of the other options?

Fill the following matrix with the cost of the algorithms you found (or inferred from the theorems used to prove Theorem 13.1).

For example, the “?” at the cell in row “input: DFA” and column “output: \varepsilon-NFA” needs to be filled with the cost of an algorithm that given a DFA A as input, needs to output an \varepsilon-NFA accepting the same language. Since DFAs are special cases of \varepsilon-NFA the algorithm is trivial, the cost is just to the cost to write down the input in the output: \mathcal{O}(n) (where DFA description of the input had length n).

	output: Regex	output: DFA	output: \varepsilon-NFA
input: Regex	🌱	?	🌱
input: DFA	?	🌱	🌱
input: \varepsilon-NFA	?	?	🌱

13.1 Closure properties

In the previous chapters we saw (or left as exercise to show) that \mathbf{Regular} is closed under union, intersection, complement, reverse, concatenation, Kleene star, homomorphisms, and inverse homomorphisms.

For each operation, the cost of computing the resulting language depends on how the input languages are presented (as regexes/DFAs/\varepsilon-NFAs) and how we want to present the output language.

Exercise 13.6 Fill the following table with the cost (in the worst case) of computing the operations (on the rows) when both the inputs and outputs are given as regexes/DFAs/\varepsilon-NFAs (as specified on the columns).

Express the cost as a function of the number of symbols (for regexes) or number of vertices (for DFAs/\varepsilon-NFAs).

For example, given two regexes r,s with n and m symbols respectively, the union of the two languages can be represented by the regex r+s with n+m+\mathcal{O}(1) symbols which is computed in \mathcal{O}(n+m) time.

	Regex	DFA	\varepsilon-NFA
Union	🌱 \mathcal{O}(n+m)	?	🌱
Intersection	?	?	?
Complement	?	🌱	?
Reverse	🌱	?	?
Concatenation	🌱	?	?
Kleene star	🌱	?	?
Homomorphism	?	?	?
Inverse homomorphism	?	?	?

The 🌱 symbol marks some operations/representation-formats that are trivial to compute.

13.2 Decision problems

In the previous chapters we saw algorithms that could be used to answer some natural decision problems on regular languages. In this section you are asked to revise them and fill the following table.

Exercise 13.7 Fill the following table with the cost (in the worst case) of computing natural decision problems (on the rows) when the description of the regular language L is given as a regex/DFA/\varepsilon-NFA (as specified on the columns).

Express the cost as a function of the number of symbols (for regexes) or number of vertices (for DFAs/\varepsilon-NFAs).

For example, “L_1=L_2?” means: given descriptions of L_1 and L_2 both as regexes/DFAs/NFAs, what is the (worst case) cost of deciding whether L_1=L_2?

	Regex	DFA	\varepsilon-NFA
Is the word w in \mathscr{L}(L)? (w is also given as input)	?	?	?
Is L=\emptyset?	?	?	?
Is L finite?	?	?	?
Is L_1=L_2?	?	?	?

You already did part of this exercise in Exercise 7.5.↩︎
In Exercise 7.4 you saw a similar exercise for the class of languages \mathbf{Finite}.↩︎
In Chapter 14, we see some explicit languages that do not belong to \mathbf{Regular}.↩︎