Loading [MathJax]/jax/output/HTML-CSS/jax.js

Partial Coursenotes for Formal Languages and Automata

Chapter 2 Week 3

| About « 2.2. Regular Grammars :: Contents :: 3.1. Identifying Non-regular Languages »

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

Contact Us || Privacy | | License « 2.2. Regular Grammars :: Contents :: 3.1. Identifying Non-regular Languages »