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

$\}$

$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:

r1+r2 is a regular expression denoting L1∪L2.
So, regular languages are closed under union.
r1r2 is a regular expression denoting L1L2.
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.

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)$ .

L1=L(M1) and  L2=L(M2)
M1=(Q,Σ,δ1,q0,F1)
M2=(Q,Σ,δ2,p0,F2)

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$

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:

L1={a∗b∗∪b∗a∗}
L2={bn∣n is even, n>0}
L1∖L2={a∗b∗}

Right Quotient (2)

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

Proof: (sketch)

∃ DFA M1=(Q,Σ,δ,q0,F) such that
L1=L(M1), and
∃ DFA M2=(Q,Σ,δ,q0,F) such that
L2=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 qi of M1, if there is a wal labeled
with any string ∈L2 to a final state in M1,
we mark qi as final in M′.

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)^*$

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$ .

$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)

$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$ .