Closure Properties of Regular Grammars¶

1. Closure Properties of Regular Grammars¶

1.1. Closure Concept¶

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.

Example 1

\(L = \{x | x \mbox{is a positive even integer}\}\)

Is \(L\) is closed under the following?

addition? Yes. [How do you know? Need a proof.]
multiplication? Yes. [How do you know? Need a proof.]
subtraction? No. \(6 - 10 = -4\). [Now you know!]
division? No. \(4 / 4 = 1\). [Now you know!]

1.2. Closure of Regular Languages¶

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: [Ask yourself: Why do we know this?]

\(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: 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.

Note

Why a DFA, will an NFA work? With difficulty: It must be a complete NFA with trap states added.

Proof: Regular languages are closed under intersection.

One simple way to prove this is using DeMorgan's Law:

\[L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\]

Here is another approach by construction.

\(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)\)

Note

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

Now, construct \(M' = (Q', \Sigma, \delta', (q_0, p_0), F')\)

\(Q' = (Q \times P)\)

\(\delta'\):

\(\delta'((q_i, p_j), a) = (q_k, p_l)\) if

\(\delta_1((q_i, a) = q_k) \in M_1\) and \(\delta_2((p_j, a) = p_l) \in M_1\).

\(F' = \{(q_i, p_j) \in Q' | q_i \in F_1\) and \(p_j \in F_2\}\)

\(w \in L(M') \Longleftrightarrow w \in L_1 \cap L_2 \Rightarrow\) is closed under intersection

Example 2

Create the DFA for the intersection of two DFAs:

\(L_1 = a^*b\) and \(L_2 = aa\{a|b\}^*\)

1.3. Regular languages are closed under these operations¶

Reversal: \(L^R\)

Difference: \(L_1 - L_2\)

Right quotient:

Definition: \(L_1 \backslash L_2 = \{x | xy \in L_1\ \mbox{for some}\ y \in L_2\}\)

In other words, it is prefixs of appropriate strings in \(L_1\).

Example 3

\(L_1 = \{a^*b^* \cup b^*a^*\}\)
\(L_2 = \{b^n | n\) is even, \(n > 0 \}\)
\(L_1/L_2 = \{a^*b^*\}\)

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

Proof: (sketch)

\(\exists\) DFA \(M = (Q, \Sigma, \delta, q_0, F)\) such that \(L_1 = L(M)\).

Construct DFA \(M'=(Q, \Sigma, \delta, q_0, F')\) (equivalent to \(M\) except for final states).

For each state \(i\) do

Make \(i\) the start state (representing \(L_i'\))

if \(L_i' \cap L_2 \ne \emptyset\) then

put \(q_i\) in \(F'\) in \(M'\)

Note

Not empty means there's a path between start and a final state.

QED.

Homomorphism:

Definition: 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 4

\(\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)^*\)

1.4. Questions about regular languages¶

\(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.

Note

Perform depth first search.

This was easy! But we will see that in other contexts that complement is not so simple to decide.
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\).

Again, in other contexts, this is impossible. For example, we will prove that its not possible to decide, in general, if two programs do the same thing.

1.5. Summary: How do we prove that a language is regular?¶

We have a number of approaches in our toolbox.

Write a DFA that accepts the language.
Write a NFA that accepts the language.
Write a regular expression that accepts the language.
Write a regular grammar tha accepts the language.
Define the language in terms of one or more known regular languages that are manipulated by operators known to be closed under for regular languages.

OpenDSA Stand-alone Modules

Chapter 0 modules

Closure Properties of Regular Grammars¶

1. Closure Properties of Regular Grammars¶

1.1. Closure Concept¶

1.2. Closure of Regular Languages¶

1.3. Regular languages are closed under these operations¶

1.4. Questions about regular languages¶

1.5. Summary: How do we prove that a language is regular?¶