2.Closure Properties§

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 = \{x \mid x\) is a positive even integer \(\}\)
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!]

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.

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{L} \Rightarrow\) closed under complementation.

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

Proof: Intersection

Proof: Regular languages are closed under intersection.

  1. DeMorgan’s Law: \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\)
(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.

More Closure Properties (1)

Regular languages are closed under these operations

Reversal: \(L^R\)

Difference: \(L_1 - L_2\)

More Closure Properties (2)

Right quotient: \(L_1 / L_2 = \{x \mid xy \in L_1\ \mbox{for some}\ y \in L_2\}\).
In other words, it is prefixs of appropriate strings in \(L_1\). Example:
\(L_1 = \{a^*b^* \cup b^*a^*\}\)
\(L_2 = \{b^n \mid n\) is even, \(n > 0 \}\)
\(L_1/L_2 = \{a^*b^*\}\)

Theorem: If \(L_1\) and \(L_2\) are regular, then \(L_1 / L_2\) is regular.

Proof: (sketch)
\(\exists\) DFA \(M = (Q, \Sigma, \delta, q_0, F)\) such that \(L_1 = L(M)\).
Construct this DFA from the DFAs for \(L_1\) and \(L_2\).
There is an algorithm for that.

More Closure Properties (3)

Homomorphism: Let \(\Sigma, \Gamma\) be alphabets. A homomorphism is a function \(h : \Sigma \rightarrow \Gamma^*\)

Homomorphism means to substitute a single letter with a string.

Example
\(\Sigma=\{a, b, c\}, \Gamma = \{0,1\}\)
\(h(a) = 11\)
\(h(b) = 00\)
\(h(c) = 0\)
\(h(bc) = h(b)h(c) = 000\)
\(h(ab^*) = h(a)h(b^*) = 11(h(b))^* = 11(00)^*\)

Questions about Reg Languages (1)

\(L\) is a regular language.
Given \(L, \Sigma, w \in \Sigma^*\), is \(w \in L\)?
Answer: Construct a FA and test if it accepts \(w\).
Is \(L\) empty?
Example: \(L = \{a^nb^m | n > 0, m > 0\} \cap \{b^na^m | n > 1, m > 1\}\) is empty.
Construct a FA. If there is a path from start state to a final state, then \(L\) is not empty.

Questions about Reg Languages (2)

Is \(L\) infinite?
Construct a FA. Determine if any of the vertices on a path from the start state to a final state are the base of some cycle. If so, then \(L\) is infinite.
Does \(L_1 = L_2\)?
Construct \(L_3 = (L_1 \cap \bar{L_2}) \cup (\bar{L_1} \cap L_2)\). If \(L_3 = \emptyset\), then \(L_1 = L_2\).