2. 3. Closure Properties of Regular Languages¶

Definition: A set is closed over a (binary) operation if, whenever the operation is applied to two members of the set, the result is a member of the set.

Consider \(L = \\) Is \(L\) is closed under the following? addition? Yes. [How do you know?] multiplication? Yes. [How do you know?] subtraction? No. \(6 - 10 = -4\) . [Now you know!] division? No. \(4 / 4 = 1\) . [Now you know!]

2. 3.2. Closure of Regular Languages (1)¶

Consider regular languages \(L_1\) and \(L_2\) . In other words, \(\exists\) regular expressions \(r_1\) and \(r_2\) such that \(L_1 = L(r_1)\) and \(L_2 = L(r_2)\) .

These we already know:

\(r_1 + r_2\) is a regular expression denoting \(L_1 \cup L_2\) . So, regular languages are closed under union.

\(r_1r_2\) is a regular expression denoting \(L_1 L_2\) . So, regular languages are closed under concatenation.

\(r_1^*\) is a regular expression denoting \(L_1^*\) . So, regular languages are closed under star-closure.

2. 3.3. Proof: Complementation¶

Proof: Regular languages are closed under complementation.

\(L_1\) is a regular language \(\Rightarrow \exists\) a DFA \(M\) such that \(L_1 = L(M)\) . Construct DFA \(M'\) such that: final states in \(M\) are nonfinal states in \(M'\) . nonfinal states in \(M\) are final states in \(M'\) . \(w \in L(M') \Longleftrightarrow w \in \bar \Rightarrow\) closed under complementation.

Why a DFA, will an NFA work? Must be NFA with trap states.

2. 3.4. Proof: Intersection¶

  1. DeMorgan’s Law: \(L_1 \cap L_2 = \overline <\overline\cup \overline>\)

(2) \(L_1\) and \(L_2\) are regular languages \(\Rightarrow \exists\) DFAs \(M_1\) and \(M_2\) such that \(L_1 = L(M_1)\) and \(L_2 = L(M_2)\) .

\(L_1 = L(M_1)\) and \(L_2 = L(M_2)\) \(M_1 = (Q, \Sigma, \delta_1, q_0, F_1)\) \(M_2 = (Q, \Sigma, \delta_2, p_0, F_2)\)

The idea is to construct a DFA so that it accepts only if both \(M_1\) and \(M_2\) accept. There is an algorithm for that.

2. 3.5. More Closure Properties (1)¶

Regular languages are closed under these operations

Reversal: \(L^R\)

Difference: \(L_1 - L_2\)