Complement

Let $A$ represent all strings, and inside $A$ there’s a language $L$. The rest part of A is called the complement of $L$, or $\bar L$

Theorem: $L$ regular ⇒ $\bar L$ regular

“Regular languages are closed under complement”

Proof: to turn $L$’s automata to $\bar L$’s, we can just flip the accept state to transition state and vice versa.

Formally:

DFA($Q,\Sigma,\delta, q_0,F$) recognizes $L$ ⇒ DFA($Q,\Sigma,\delta, q_0,Q-F$) recognizes $\bar L$

Union + Intersection

$L’ \cup L’’ = \{w:w\in L' \text{ or }w\in L'' \}$

$L’ \cap L’’ = \{w:w\in L' \text{ and }w\in L'' \}$

Theorem: If L’ and L’’ are regular, then so are:

a) $L’ \cup L’’$

having an indirect state that guide to those 2 DFA or NFA

b) $L’ \cap L’’$

$L’, L’’$ regular ⇒ $\bar L’, \bar L’’$ regular

⇒ $\bar L’\cup \bar L’’$ regular

⇒ $\bar{\bar L’\cup \bar L’’}$ regular

⇒ $L’ \cap L’’$ regular

“Regular languages are closed under union and intersection”

Formal Proof:

DFA for L’: ($Q',\Sigma,\delta', q_0',F'$)

DFA for L’’: $(Q'',\Sigma,\delta'', q_0'',F'')$

DFA for $L’ \cup L’’$: $(Q'\times Q'', \Sigma, \delta, (q_0',q_1'),(F'\times Q'')\cup(Q'\times F''))$

where $\delta((q',q''),\sigma) = (\delta'(q',\sigma),\delta''(q'',\sigma))$

DFA for $L’ \cap L’’$: $(Q'\times Q'', \Sigma, \delta, (q_0',q_1'),(F'\times F''))$

Corollary: If L1, L2,...Ln are regular

so are $L1 \cup L2 \cup ... \cup Ln$

and $L1 \cap L2 \cap ... \cap Ln$

Corollary: Every finite language is regular

Let L be finite

L = $\cup_{w\in L}\{w\}$

each $w$ is a singleton language that contains only one string, and each of them is regular