4.6.1
Intuition Bada picture (YEH kyun exist karta hai)Har computer "baat" — passwords, programs, DNA, protocols — sirf symbols ki ek line hoti hai. Theory of Computation ko ek solid vocabulary chahiye taaki kisi bhi aisi symbol-lines ki collection ke baare mein baat kar sake. Isliye hum ek 3-floor tower banate hain:
Alphabet → String → Language .
Ek alphabet hamare liye Lego bricks deta hai.
Ek string ek cheez hai jo hum bricks se banate hain.
Ek language un allowed cheezein ka set hai jo humne banaye.
Is course mein baaki sab kuch (DFA, regex, grammars, Turing machines) ek aisi machine hai jo decide karti hai ki kaunsi strings ek language mein belong karti hain . Toh ye definitions pakad lo aur baaki sab click karega.
Ek alphabet , jise Σ symbols ka ek finite, non-empty set hota hai.
Finite — tum har symbol list kar sakte ho.Non-empty — kam se kam ek symbol exist karta hai.Symbol — ek atomic, indivisible token.
YEH finite & non-empty kyun? Agar Σ Σ
Binary: Σ = { 0 , 1 }
English-ish: Σ = { a , b , c , … , z }
DNA: Σ = { A , C , G , T }
Single symbol: Σ = { a }
Σ string (ya word ) Σ symbols ka ek finite ordered sequence hota hai.
Empty string , jise ε koi symbol nahi hota aur yeh har alphabet par ek valid string hai.
Definition String ki length∣ w ∣ w ∣ ε ∣ = 0 w = 0110 ∣ w ∣ = 4
Hum chahte hain ki concatenation ki length add ho: ∣ x y ∣ = ∣ x ∣ + ∣ y ∣ ∣ w ∣
Base: ∣ ε ∣ = 0 Step: ek non-empty string hai "koi string x a w = x a ∣ x a ∣ = ∣ x ∣ + 1 w = a 1 a 2 … a n ∣ w ∣ = n 1 + 1 + ⋯ + 1 = n
Yeh ( Σ ∗ , concat ) ε monoid banata hai.
Definition Reversal & substring
Reversal w R ε R = ε ( x a ) R = a ( x R ) ( 011 ) R = 110 ( x y ) R = y R x R
y substring hai w w = x y z x , z Prefix : w = y z Suffix : w = x y
Definition Kleene star aur plus
Σ k exactly k ka set.==Σ ∗ = ⋃ k ≥ 0 Σ k ε samait .
==Σ + = ⋃ k ≥ 1 Σ k ≥ 1 ε exclude ).
Relation: Σ ∗ = Σ + ∪ { ε }
Σ language L Σ ∗ koi bhi subset hota hai: L ⊆ Σ ∗ set hai.
Intuition "Any subset" kyun?Ek "language" exactly hai "inputs ka set jo hum accept karte hain." Definition level par koi restriction nahi hoti — restrictions (regular, context-free…) baad mein aati hain aur classify karti hain ki kaunsi languages ek diya hua machine recognise kar sakta hai.
Σ = { 0 , 1 }
L 1 = ∅ empty language (kuch accept nahi karta). ∣ L 1 ∣ = 0 L 2 = { ε } sirf empty string accept karta hai. ∣ L 2 ∣ = 1 (≠ ∅ L 3 = { w : w has even length } L 4 = Σ ∗
∅ { ε } ε Galat feeling: "ε ∅ { ε } Yeh sahi kyun lagta hai: teeno sound karte hain "emptiness" ki tarah.
Fix — yeh alag floors par rehte hain:
ε string hai (length 0). Ek word.{ ε } language (set) hai jisme ek word hai. ∣ { ε } ∣ = 1 ∅ language hai jisme zero words hain. ∣ ∅ ∣ = 0 ∅ { ε } blank sheet wala box; ε
Σ ∗ Yeh sahi kyun lagta hai: Σ ∗ [ 0 , 1 ] Fix: Reals correspond karte hain infinite strings se. Σ ∗ finite strings hain, toh hum unhe length se list kar sakte hain → countable . (Saari languages ka set 2 Σ ∗ is uncountable — yahi "kuch languages undecidable hain" ka seed hai.)
Σ = { a , b } Σ 2 ∣ Σ 2 ∣ = 2 2 = 4 Yeh step kyun? Do positions, 2 choices each, multiply karo.
List (canonical order): aa , ab , ba , bb Order kyun? Length phir alphabetical → guarantee deta hai ki koi miss na ho.
ε ∈ L L = { w : ∣ w ∣ is even } ∣ ε ∣ = 0 Kyun? Empty string mein koi symbol nahi hai. 0 haan , ε ∈ L Steel-man: kehne ka mann karta hai "koi string nahi ⇒ kisi length-language mein nahi," lekin 0 ek legitimate even number hai.
L 1 L 2 L 1 = { 0 , 01 } L 2 = { 1 , ε } x ∈ L 1 y ∈ L 2 0 ⋅ 1 = 01 0 ⋅ ε = 0 01 ⋅ 1 = 011 01 ⋅ ε = 01 L 1 L 2 = { 0 , 01 , 011 } Ek copy kyun drop ki? 01
∣ w R ∣ = ∣ w ∣ Kyun? Positions par bijection ⇒ same count. Toh ∣ w R ∣ = ∣ w ∣
Recall Feynman: ek 12-saal ke bacche ko explain karo (hidden — pehle khud try karo!)Alphabet ko ek letter-stamps ka dibba socho (maano sirf 0 aur 1). Ek string ek word hai jo tum stamp karte ho, jaise 0110 — aur tum kuch bhi stamp nahi kar sakte, woh blank word ε language ek club hai: yeh ek list hai ki kaunse words allowed hain. Empty club ∅ { ε }
Mnemonic Tower & empties yaad rakho"A SLeeping computer" → A lphabet → S tring → L anguage (bricks → wall → allowed walls ka blueprint).
Empties: "∅ has 0, {ε} has 1, ε is the brick." Boxes count karo, blanks nahi.
Alphabet Σ Ek finite , non-empty set of symbols .
Σ Σ
ε Empty string (zero symbols); ∣ ε ∣ = 0
String length ki recursive definition. ∣ ε ∣ = 0 ∣ x a ∣ = ∣ x ∣ + 1
Σ ∗ Σ ε
Σ + Σ ∗ Saari non-empty strings; Σ ∗ = Σ + ∪ { ε }
Σ k ∣Σ ∣ k k ∣Σ∣
Σ L Koi bhi subset L ⊆ Σ ∗
∅ { ε } ∅ ∣ ∅ ∣ = 0 { ε } ∣ { ε } ∣ = 1
Σ ∗ Countably infinite (sirf finite-length strings; shortlex order se list karo).
L 1 L 2 { x y : x ∈ L 1 , y ∈ L 2 }
∅ ∗ { ε } L 0 = { ε }
w n n ∣ w ∣
Kya concatenation commutative hai? Associative? Commutative nahi (01 = 10 ( x y ) z = x ( y z )
( x y ) R y R x R
Regular Languages — languages L ⊆ Σ ∗ Finite Automata (DFA NFA) — machines jo ek language mein membership decide karti hain.Regular Expressions — Σ ∪ ∗ Context-Free Grammars — regular se aage ki languages generate karte hain.Countability and Diophantine Diagonalization — kyun 2 Σ ∗ Pumping Lemma — yahan prove ki gayi string length & concatenation structure use karta hai.
