Closure Properties of Regular Grammars

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 that operation is applied to any 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? You need a proof.]
multiplication? Yes. [How do you know? You need a proof.]
subtraction? No. \(6 - 10 = -4\). [Now you know!]
division? No. \(4 / 4 = 1\). [Now you know!]

Notice the difference between the requirement to determine that an operation is closed (need a proof covering all cases) and versus recognizing that the operation is not closed (just need a counter-example).

1.2.

Closure of Regular Languages¶

Consider regular languages \(L_1\) and \(L_2\). Since they are regular languages, we know that there exist 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.

Theorem: Regular languages are closed under complementation.

Proof:

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

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

Theorem: Regular languages are closed under intersection.

Proof:

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, therefore there
exist 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

Settings

Saving...

Server Error
Resubmit

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 \backslash L_2 = \{a^*b^*\}\)

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

Proof: (sketch)

There exists a 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 the start state to any final state, then \(L\) is not empty.

Note

Perform depth first search on the graph beginning with the start state.
Is the complement of \(L\) regular?

Answer: Simply take the DFA and reverse the final and non-final states.

This was easy! But we will see 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.

Note: This idea of cycles in DFAs will be important later!
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, whether two representations for computation do the same thing can be impossible to answer. 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 that accepts the language.
Define the language in terms of one or more known regular languages that are manipulated by operators known to be closed for regular languages.