2.3. Closure Properties of Regular Languages¶
2.3.1. 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!]
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{L} \Rightarrow\) closed under complementation.Why a DFA, will an NFA work? Must be NFA with trap states.
2.3.4. Proof: Intersection¶
Proof: Regular languages are closed under intersection.
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.
2.3.5. More Closure Properties (1)¶
Regular languages are closed under these operations
Reversal: \(L^R\)
Difference: \(L_1 - L_2\)
2.3.6. Right Quotient (1)¶
Right quotient: \(L_1 \backslash 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 \backslash L_2 = \{a^*b^*\}\)
2.3.7. Right Quotient (2)¶
Theorem: If \(L_1\) and \(L_2\) are regular, then \(L_1 \backslash L_2\) is regular.
Proof: (sketch)\(\exists\) DFA \(M1 = (Q, \Sigma, \delta, q_0, F)\) such that \(L_1 = L(M1)\), and \(\exists\) DFA \(M2 = (Q, \Sigma, \delta, q_0, F)\) such that \(L_2 = L(M2)\).Construct DFA \(M'\) from M1 and M2. This turns out to be identical to M1, except for altering the set of final states.For each state \(q_i\) of M1, if there is a wal labeled with any string \(\in L_2\) to a final state in M1, we mark \(q_i\) as final in \(M'\).
2.3.8. Homomorphism¶
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)^*\)
2.3.9. 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.
2.3.10. 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\).
