Regular languages — closed under union, intersection, complement, concatenation, Kleene star

4.6.6 · Coding › Theory of Computation

Closure KYA hai (aur hum KYUN care karte hain)

KYUN care karein? Closure se aap scratch se machine design kiye bina ek language ko regular prove kar sakte ho — aap use jaani-pehchani regular pieces mein todh lete ho. Yeh proof-by-contradiction ko bhi power deta hai: agar regular languages ko combine karne se ek jaani-hui non-regular language milti, to original regular nahi ho sakti thi.

Master tool: ek machine banao

Har proof ka yahi skeleton hai: assume karo ki inputs ke liye DFAs/NFAs exist karte hain, phir result ke liye ek nayi machine construct karo. Do construction techniques sab kaam karti hain:

Product construction (do DFAs ko parallel mein chalao) → union, intersection.
Epsilon-glue construction (NFAs ko $ε$ -transitions se jodo) → concatenation, star, aur aasaan union.

Figure — Regular languages — closed under union, intersection, complement, concatenation, Kleene star

1. Complement — accept states flip karo

Derivation (KAISE): Kisi bhi string $w$ ke liye, DFA ka run $\hat{δ} (q_{0}, w)$ ek unique state $s$ mein khatam hota hai.

$w \in A ⟺ s \in F$ .
$\overline{M}$ mein, $w$ accept hogi $⟺ s \in Q ∖ F ⟺ s \in / F ⟺ w \in / A$ . Isliye $L (\overline{M}) = \overline{A}$ . ∎

2. Intersection — product construction

Derivation (KAISE): $∣ w ∣$ par induction se, $\hat{δ} ((a_{0}, b_{0}), w) = (\hat{δ}_{A} (a_{0}, w), \hat{δ}_{B} (b_{0}, w))$ . Pair accepting hai $⟺$ pehla coordinate $\in F_{A}$ aur doosra $\in F_{B}$ $⟺ w \in A$ aur $w \in B$ . ∎

3. Union — do clean tarike

4. Concatenation — end-to-start glue karo

$M_{A}$ ke har accept state se KYUN? Kyunki prefix $x$ unme se kisi par bhi khatam ho sakta hai; har ek "A finish karo aur B shuru karo" ke liye valid jagah hai.

5. Kleene star — loop back karo, empty accept karo

Worked examples

Recall Feynman: 12-saal ke bachche ko explain karo

Socho ki har "machine" ek chhota robot hai jo ek string ko letter by letter padhta hai aur end mein YES ya NO bolta hai. Complement: wohi robot rakho lekin uske YES aur NO buttons badal do. AND / OR: do robots ko side by side chipkao aur unhe same letters saath mein padhne do; ek referee YES bolta hai agar dono (ya koi ek) khush hon. Concatenation: robot A pehla hissa padhta hai, phir secretly baaki hissa robot B ko de deta hai — lekin use guess karna hota hai kahaan dena hai. Star (repeat): jab robot A ek copy finish karta hai, woh apne start par wapas teleport ho jaata hai ek aur copy padhne ke liye, jitni baar chahe (zero baar = empty string bilkul theek hai). Kyunki hum hamesha result ke liye ek robot bana sakte hain, result abhi bhi ek "regular" cheez hai.

Flashcards

"Regular languages union ke under closed hain" ka matlab kya hai?

Agar

A, B

regular hain to

A \cup B

regular hai (unhe combine karne par aap class ke andar rehte ho).

Do DFAs ke intersection ke liye construction?

Product construction: states

Q_{A} \times Q_{B}

, transition componentwise, accept =

F_{A} \times F_{B}

Product machine se union ke liye accept set?

(F_{A} \times Q_{B}) \cup (Q_{A} \times F_{B})

— accept agar kam se kam ek coordinate final ho.

Ek regular language ko complement kaise karein?

Ek DFA lo (pehle determinize karo agar NFA ho), phir accept aur non-accept states swap karo:

F \to Q ∖ F

NFA mein sirf accept states swap karke complement kyun nahi ho sakta?

Ek NFA ek hi input par dono accepting aur non-accepting runs rakh sakta hai; swapping correctness tod deti hai. Pehle determinize karna zaroori hai.

Concatenation

A B

ke liye construction?

M_{A}

ke har accept state se

M_{B}

ke start tak

ε

-transitions add karo; naye accepts =

F_{B}

Kleene star

A^{*}

ke liye construction?

Naya start/accept state

s_{0}

ε \to a_{0}

ke saath; har purane accept state se

a_{0}

tak

ε

; accept =

{s_{0}} \cup F_{A}

Star ke liye purane start state ko accepting banane ki jagah fresh start state KYUN?

a_{0}

mein loop-back edges mid-words ko galat accept kar sakti hain; ek fresh

s_{0}

cleanly sirf

ε

handle karta hai aur restarts karta hai.

Complement+intersection se union closure derive karo.

A \cup B = \overline{\overline{A} \cap \overline{B}}

(De Morgan), isliye complement+intersection ke under closure union deta hai.

Closure ka use ek language ko non-regular PROVE karne mein kaise hota hai?

Ek regular language ke saath intersect/complement karo taaki use ek jaani-pehchani non-regular language (jaise

a^{n} b^{n}

) tak reduce kar sako; pumping lemma se contradiction.

Product DFA dono machines ko sahi se KYUN track karta hai?

Induction se:

\hat{δ} ((a_{0}, b_{0}), w) = (\hat{δ}_{A} (a_{0}, w), \hat{δ}_{B} (b_{0}, w))

, isliye pair dono runs ko exactly mirror karta hai.

Connections

Deterministic Finite Automata (DFA) — complement ke liye zaroori (total, deterministic).
Nondeterministic Finite Automata (NFA) — $ε$ -glue concat/star/union ko power deta hai.
Subset Construction (NFA to DFA) — isliye complement mein pehle determinization chahiye.
Regular Expressions — union/concat/star literally regex operators hain.
Pumping Lemma for Regular Languages — regularity disprove karne ka partner tool.
De Morgan's Laws — union/intersection/complement ko link karta hai.
Product Construction — intersection, union, aur difference ke liye reuse hota hai.