Concatenation of regular languages

Let L₁, L₂ be two regular languages. We will prove that their concatenation L = L₁ ∘ L₂ is also a regular language.

What concatenation is

Concatenating the two strings “010” and “1111” gives the string “0101111”. Concatenating languages therefore produces a new language, which we build by concatenating every string from one language with every string from the other. We denote the concatenation of two strings or two languages with a small circle: ∘. We can then define the concatenation of the languages L₁ and L₂ as follows:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Idea of the proof

We have two regular languages L₁, L₂ and two automata that accept these languages:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

We construct a non-deterministic automaton A = ⟨Q, Σ, δ, q, F⟩ that will “contain” both automata A₁ and A₂. The basic idea is that we start reading the string with the automaton A₁, and when A₁ reaches an accepting state, we try to accept the rest of the string with the automaton A₂. If this automaton accepts that part of the string too, then the automaton A accepts the string.

Example

Let A₁ be this automaton, which accepts non-empty strings made up only of zeros, and strings made up of a 1 followed only by zeros (1, 10, 100, …):

and let A₂ be this automaton, which accepts strings that end in 01:

We join the automata by adding epsilon transitions from all the accepting states of A₁ to the start state of A₂, and then turning the accepting states of A₁ into ordinary states. The start state of the whole new automaton will be the start state of A₁:

How will the automaton work? We start by simulating the automaton A₁. If we move to a former accepting state q₁ or q₂, we know that A₁ accepts part of this string. For the whole string to belong to the language L₁ ∘ L₂, the rest of the string must still be accepted by the second automaton A₂ – that is why epsilon transitions lead from all the former accepting states to the original start state of A₂.

As an example, take the string 0001. It belongs to the concatenation of both languages, because the string can be formed by concatenating the strings 00 ∘ 01. But it can equally be formed by concatenating the strings 0 ∘ 001. In our automaton we can simulate both ways. The automaton can follow this path:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

On this path the automaton first “accepts” the part 00 of the string and then the part 01. Or it can follow this path:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

and the automaton would first “accept” the part 0 and then the part 001. In both cases we of course end up in the accepting state p₂.

Formal construction

Once more: we have two regular languages L₁, L₂ and two automata that accept these languages:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

We construct a non-deterministic automaton A = ⟨Q, Σ, δ, q, F⟩ for which the following holds:

• Q = Q₁ ∪ Q₂ (we also assume that Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

We build the transition function δ step by step:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{if}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{if}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{if}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{if}& q\in Q_2\end{array}$$

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools