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$

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:

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

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

Proof: (sketch)

∃ DFA M=(Q,Σ,δ,q0,F) such that
L1=L(M).
Construct this DFA from the DFAs for L1 and L2.
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$ .

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