Regular Language

A language (set of formulae/strings) is regular if every word in it is accepted by a deterministic finite state automata.

Definition §

Regular Language

Let $A$ be a language. $A$ is a regular language if there exists at least one deterministic finite automaton (DFA), $M$ that recognises $A$:

$$\text{A is regular}⟺\exists \text{DFA M s.t. }L(M)=A$$

What does recognise mean?

Regular Operations §

Most operations on languages are closed over regularity or regular-preserving. That is, applying these operations on a regular language will always result in another regular language. The proofs for such properties usually involve the construction of a new DFA or NFA, since if we can construct a DFA that only recognises a set of strings, then the language corresponding to that set of strings is regular.

The following operations preserve regularity (See Theorems for more info):

• Union
• Intersection
• Complement
• Concatenation
• Kleene Star
• Set Difference
• Reversal

Limitations §

While every finite language is regular, there are some infinite languages that are non-regular.

Take the language $L=\{0^n{1}^n|n\in \mathbb{N}\}$

To prove this language is regular, we would need a DFA that can keep track of how many occurrences of $1$ it encountered, so that it is equal to the number of occurrences of 0.

However, DFAs are ‘memoryless’, so this is not possible!

Examples §

• ${\Sigma }^{\ast }$ is regular

This is because $\Sigma =\{a_1,a_2,\dots a_n\}$ is finite and can be represented by the regex $R=(a_1\cup a_2\cup \cdots \cup a_n)$. Then $R^{\ast }$ produces a valid regex, and hence it describes a regular language.

Theorems §

T1: Every finite language is regular

Let $L$ be a language.

$$\text{L is finite}⟹\text{L is regular}$$

Finiteness here means that $L$ has a finite number of strings, and is some ‘closed’ set.

C1: Regularity is closed under any boolean combination

From the theorems below, we can construct an equivalent ‘mapping’ that maps set operations with logical connectives. That is, just like we can create a complex predicate using logical connectives over atoms, we can construct a new language using a combination of languages.

If all the ‘atomic’ languages used to make a new language are regular, then the new language is also regular

T2: Regularity is closed under union ^t2

Let $A,B$ be two regular languages. Then, the union (with respect to languages), preserves regularity:

$$\text{A,B are regular}⟹A\cup B\text{ is regular}$$

The contrapositive yields:

$$A\cup B\text{ is non-regular}⟹\text{A is non-regular}\vee \text{B is non-regular}$$

Proof

• We know, by definition of regular languages, that there exists DFAs that recognise $A$ and $B$. Let $A=L(M)$ and $B=L(N)$ (i.e. $A,B$ are recognised by $M,N$, respectively).
• We can construct an NFA, $P$ using $M$ and $N$:
• $P$ accepts everything that $M$ and $N$ accept, (because we are essentially running them both in parallel)
• Then, $P$ recognises $A\cup B$, i.e. $L(P)=A\cup B$
• By the theorem of equivalence, there is an equivalent DFA, $D\sim P$ that also recognises $A\cup B$.
• Since we have a recognising DFA, $A\cup B$ is a regular language.

T3: Complement of a regular language is regular ^t3

Let $L$ be a regular language. Then, the complement of $L$, given by $L^C$ is regular:

$$\text{L is regular}⟹\text{LC is regular}$$

Proof

• Since $L$ is regular, there exists a DFA, $M$ that recognises $L$.
• We can construct a new DFA, $M^{\ast }$, which ‘flips’ all the accepting states of $M$. That is, any accept state in $M$ becomes a non-accepting state in $M^{\ast }$ and vice versa. Then we have:
• $M^{\ast }$ accepts every string that $M$ would reject, and hence it recognises $L^C$
• Thus, $L^C$ is regular. %%🖋 Edit in Excalidraw, and the dark exported image%%

T4: Regularity is closed under concatenation ^t4

Let $A,B$ be two regular languages. Then, the operation of concatenation preserves regularity:

$$\text{A,B are regular}⟹A\circ B\text{ is regular}$$

Proof

• We know, by definition of regular languages, that there exists DFAs that recognise $A$ and $B$. Let $A=L(M)$ and $B=L(N)$ (i.e. $A,B$ are recognised by $M,N$, respectively).
• We can construct an NFA, $P$ using $M$ and $N$: %%🖋 Edit in Excalidraw, and the dark exported image%%
• Essentially, $P$ is made by connecting the initial states of $N$ to the accepting/final states of $M$ by epsilon transitions. This ensures none of the input string gets consumed when are checking the second section.
• Then, $P$ recognises $A\circ B$, i.e. $L(P)=A\circ B$
• By the theorem of equivalence, there is an equivalent DFA, $D\sim P$ that also recognises $A\circ B$.
• Since we have a recognising DFA, $A\circ B$ is a regular language.

T5: Regularity is closed under Kleene star ^t5

Let $L$ be a regular language. Then, the Kleene star operation preserves regularity:

$$\text{L is regular}⟹\text{L∗ is regular}$$

Proof

• Since $L$ is regular, there exists a DFA, $M$ that recognises $L$.
• We can construct an NFA, $P$ that ‘loops over’ $M$ using epsilon transitions: %%🖋 Edit in Excalidraw, and the dark exported image%%
• Then, $P$ recognises $L^{\ast }$
• By the theorem of equivalence, there is an equivalent DFA, $D\sim P$ that also recognises $L^{\ast }$.
• Since we have a recognising DFA, $L^{\ast }$ is a regular language.

Proof (Concise):

• The Kleene star can be defined as the infinite union of concatenations.
• If $L$ is regular, than by theorem 2 and theorem 4, $L\cup L$ and $L\circ L$ is also regular
• $L^n=\underset{n\text{ times}}{\underbrace{L\circ L\circ L\circ L}}$ is regular
• Then $L^{\ast }=L^0\cup L^1\cup \dots L^{\infty }$ is regular

T6: More regular-preserving operations #TODO ^t6

The following operations all preserve regularity:

• Intersection
• Set Difference
• Reversal