Intuition The big picture (WHY this exists)Every computer "talk" — passwords, programs, DNA, protocols — is just symbols written in a row . The Theory of Computation needs a rock-solid vocabulary to talk about any such collection of symbol-rows. So we build a 3-floor tower:
Alphabet → String → Language .
An alphabet gives us the Lego bricks .
A string is one thing we build from bricks.
A language is a set of allowed things we built.
Everything else in this course (DFA, regex, grammars, Turing machines) is a machine that decides which strings belong to a language . So nail these definitions and the rest clicks.
An alphabet , written Σ \Sigma Σ finite, non-empty set of symbols .
Finite — you can list every symbol.Non-empty — at least one symbol exists.Symbol — an atomic, indivisible token.
WHY finite & non-empty? If Σ \Sigma Σ Σ \Sigma Σ
Binary: Σ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 }
English-ish: Σ = { a , b , c , … , z } \Sigma=\{a,b,c,\dots,z\} Σ = { a , b , c , … , z }
DNA: Σ = { A , C , G , T } \Sigma=\{A,C,G,T\} Σ = { A , C , G , T }
Single symbol: Σ = { a } \Sigma=\{a\} Σ = { a }
A string (or word ) over Σ \Sigma Σ finite ordered sequence of symbols taken from Σ \Sigma Σ empty string , written ε \varepsilon ε no symbols and is a valid string over every alphabet.
Definition Length of a string∣ w ∣ |w| ∣ w ∣ w w w ∣ ε ∣ = 0 |\varepsilon| = 0 ∣ ε ∣ = 0 w = 0110 w = 0110 w = 0110 ∣ w ∣ = 4 |w| = 4 ∣ w ∣ = 4
We want concatenation length to add up: ∣ x y ∣ = ∣ x ∣ + ∣ y ∣ |xy| = |x| + |y| ∣ x y ∣ = ∣ x ∣ + ∣ y ∣ ∣ w ∣ |w| ∣ w ∣
Base: ∣ ε ∣ = 0 |\varepsilon| = 0 ∣ ε ∣ = 0 Step: a non-empty string is "some string x x x a a a w = x a w = xa w = x a ∣ x a ∣ = ∣ x ∣ + 1 |xa| = |x| + 1 ∣ x a ∣ = ∣ x ∣ + 1 w = a 1 a 2 … a n w = a_1 a_2 \dots a_n w = a 1 a 2 … a n ∣ w ∣ = 1 + 1 + ⋯ + 1 ⏟ n = n |w| = \underbrace{1+1+\dots+1}_{n} = n ∣ w ∣ = n 1 + 1 + ⋯ + 1 = n
This makes ( Σ ∗ , concat ) (\Sigma^*, \text{concat}) ( Σ ∗ , concat ) monoid with identity ε \varepsilon ε
Definition Reversal & substring
Reversal w R w^R w R ε R = ε \varepsilon^R=\varepsilon ε R = ε ( x a ) R = a ( x R ) (xa)^R = a\,(x^R) ( x a ) R = a ( x R ) ( 011 ) R = 110 (011)^R = 110 ( 011 ) R = 110 ( x y ) R = y R x R (xy)^R = y^R x^R ( x y ) R = y R x R
y y y substring of w w w w = x y z w = x\,y\,z w = x y z x , z x,z x , z Prefix : w = y z w = y\,z w = y z Suffix : w = x y w = x\,y w = x y
Definition Kleene star and plus
Σ k \Sigma^k Σ k all strings of length exactly k k k .==Σ ∗ = ⋃ k ≥ 0 Σ k \Sigma^* = \bigcup_{k\ge 0} \Sigma^k Σ ∗ = ⋃ k ≥ 0 Σ k including ε \varepsilon ε
==Σ + = ⋃ k ≥ 1 Σ k \Sigma^+ = \bigcup_{k\ge 1} \Sigma^k Σ + = ⋃ k ≥ 1 Σ k ≥ 1 \ge 1 ≥ 1 excludes ε \varepsilon ε Σ ∗ = Σ + ∪ { ε } \Sigma^* = \Sigma^+ \cup \{\varepsilon\} Σ ∗ = Σ + ∪ { ε }
A language L L L Σ \Sigma Σ any subset of Σ ∗ \Sigma^* Σ ∗ L ⊆ Σ ∗ L \subseteq \Sigma^* L ⊆ Σ ∗ set of strings .
Intuition WHY "any subset"?A "language" is exactly "the set of inputs we accept." There is no restriction at the definition level — restrictions (regular, context-free…) come later and classify which languages a given machine can recognise.
Worked example Languages overΣ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 }
L 1 = ∅ L_1 = \varnothing L 1 = ∅ empty language (accepts nothing). ∣ L 1 ∣ = 0 |L_1|=0 ∣ L 1 ∣ = 0 L 2 = { ε } L_2 = \{\varepsilon\} L 2 = { ε } only the empty string. ∣ L 2 ∣ = 1 |L_2|=1 ∣ L 2 ∣ = 1 (≠ ∅ \varnothing ∅ L 3 = { w : w has even length } L_3 = \{w : w \text{ has even length}\} L 3 = { w : w has even length } L 4 = Σ ∗ L_4 = \Sigma^* L 4 = Σ ∗
∅ \varnothing ∅ { ε } \{\varepsilon\} { ε } ε \varepsilon ε Wrong feeling: "ε \varepsilon ε ∅ \varnothing ∅ { ε } \{\varepsilon\} { ε } Why it feels right: all three sound like "emptiness."
The fix — they live on different floors:
ε \varepsilon ε string (length 0). One word.{ ε } \{\varepsilon\} { ε } language (a set) containing one word. ∣ { ε } ∣ = 1 |\{\varepsilon\}| = 1 ∣ { ε } ∣ = 1 ∅ \varnothing ∅ language containing zero words. ∣ ∅ ∣ = 0 |\varnothing| = 0 ∣ ∅ ∣ = 0 ∅ \varnothing ∅ { ε } \{\varepsilon\} { ε } blank sheet ; ε \varepsilon ε
Σ ∗ \Sigma^* Σ ∗ Why it feels right: Σ ∗ \Sigma^* Σ ∗ [ 0 , 1 ] [0,1] [ 0 , 1 ] Fix: Reals correspond to infinite strings. Σ ∗ \Sigma^* Σ ∗ finite strings, so we can list them by length → countable . (The set of all languages 2 Σ ∗ 2^{\Sigma^*} 2 Σ ∗ is uncountable — that's the seed of "some languages are undecidable.")
Worked example E1 — Count and listΣ 2 \Sigma^2 Σ 2 Σ = { a , b } \Sigma=\{a,b\} Σ = { a , b } ∣ Σ 2 ∣ = 2 2 = 4 |\Sigma^2| = 2^2 = 4 ∣ Σ 2 ∣ = 2 2 = 4 Why this step? Two positions, 2 choices each, multiply.
List (canonical order): a a , a b , b a , b b aa, ab, ba, bb aa , ab , ba , bb Why order? Length then alphabetical → guarantees we miss none.
ε ∈ L \varepsilon \in L ε ∈ L L = { w : ∣ w ∣ is even } L=\{w : |w| \text{ is even}\} L = { w : ∣ w ∣ is even } ∣ ε ∣ = 0 |\varepsilon| = 0 ∣ ε ∣ = 0 Why? Empty string has no symbols. 0 0 0 yes , ε ∈ L \varepsilon\in L ε ∈ L Steel-man: tempting to say "no string ⇒ not in any length-language," but 0 is a legitimate even number.
Worked example E3 — ComputeL 1 L 2 L_1 L_2 L 1 L 2 L 1 = { 0 , 01 } L_1=\{0,01\} L 1 = { 0 , 01 } L 2 = { 1 , ε } L_2=\{1,\varepsilon\} L 2 = { 1 , ε } x ∈ L 1 x\in L_1 x ∈ L 1 y ∈ L 2 y\in L_2 y ∈ L 2 0 ⋅ 1 = 01 0\cdot1=01 0 ⋅ 1 = 01 0 ⋅ ε = 0 0\cdot\varepsilon=0 0 ⋅ ε = 0 01 ⋅ 1 = 011 01\cdot1=011 01 ⋅ 1 = 011 01 ⋅ ε = 01 01\cdot\varepsilon=01 01 ⋅ ε = 01 L 1 L 2 = { 0 , 01 , 011 } L_1L_2=\{0,\,01,\,011\} L 1 L 2 = { 0 , 01 , 011 } Why drop a copy? 01 01 01
∣ w R ∣ = ∣ w ∣ |w^R| = |w| ∣ w R ∣ = ∣ w ∣ Why? Bijection on positions ⇒ same count. So ∣ w R ∣ = ∣ w ∣ |w^R|=|w| ∣ w R ∣ = ∣ w ∣
Recall Feynman: explain to a 12-year-old (hidden — try first!)Think of an alphabet as a box of letter-stamps (say only 0 and 1). A string is one word you stamp out, like 0110 — and you're even allowed to stamp nothing , that blank word is called ε \varepsilon ε language is a club : it's a list of which words are allowed in. The empty club ∅ \varnothing ∅ { ε } \{\varepsilon\} { ε }
Mnemonic Remember the tower & the empties"A SLeeping computer" → A lphabet → S tring → L anguage (bricks → wall → blueprint of allowed walls).
Empties: "∅ has 0, {ε} has 1, ε is the brick." Count the boxes, not the blanks.
What three properties define an alphabet Σ \Sigma Σ A finite , non-empty set of symbols .
Define a string over Σ \Sigma Σ A finite ordered sequence of symbols from
Σ \Sigma Σ (possibly empty).
What is ε \varepsilon ε The empty string (zero symbols);
∣ ε ∣ = 0 |\varepsilon|=0 ∣ ε ∣ = 0 .
Recursive definition of string length. ∣ ε ∣ = 0 |\varepsilon|=0 ∣ ε ∣ = 0 and
∣ x a ∣ = ∣ x ∣ + 1 |xa|=|x|+1 ∣ x a ∣ = ∣ x ∣ + 1 .
What is Σ ∗ \Sigma^* Σ ∗ The set of all finite strings over
Σ \Sigma Σ , including
ε \varepsilon ε .
What is Σ + \Sigma^+ Σ + Σ ∗ \Sigma^* Σ ∗ All non-empty strings;
Σ ∗ = Σ + ∪ { ε } \Sigma^*=\Sigma^+\cup\{\varepsilon\} Σ ∗ = Σ + ∪ { ε } .
How many strings of length k k k Σ \Sigma Σ ∣ Σ ∣ k |\Sigma|^{k} ∣Σ ∣ k (each of
k k k positions has
∣ Σ ∣ |\Sigma| ∣Σ∣ choices).
Definition of a language L L L Σ \Sigma Σ Any subset
L ⊆ Σ ∗ L\subseteq\Sigma^* L ⊆ Σ ∗ .
Difference between ∅ \varnothing ∅ { ε } \{\varepsilon\} { ε } ∅ \varnothing ∅ has 0 strings (
∣ ∅ ∣ = 0 |\varnothing|=0 ∣ ∅ ∣ = 0 );
{ ε } \{\varepsilon\} { ε } has 1 string (
∣ { ε } ∣ = 1 |\{\varepsilon\}|=1 ∣ { ε } ∣ = 1 ).
Is Σ ∗ \Sigma^* Σ ∗ Countably infinite (only finite-length strings; list by shortlex order).
Define L 1 L 2 L_1L_2 L 1 L 2 { x y : x ∈ L 1 , y ∈ L 2 } \{xy : x\in L_1,\ y\in L_2\} { x y : x ∈ L 1 , y ∈ L 2 } .
What is ∅ ∗ \varnothing^* ∅ ∗ { ε } \{\varepsilon\} { ε } , because
L 0 = { ε } L^0=\{\varepsilon\} L 0 = { ε } is always included.
Length of w n w^n w n Is concatenation commutative? Associative? Not commutative (
01 ≠ 10 01\ne10 01 = 10 ); associative (
( x y ) z = x ( y z ) (xy)z=x(yz) ( x y ) z = x ( y z ) ).
What is ( x y ) R (xy)^R ( x y ) R
Regular Languages — the first restricted class of languages L ⊆ Σ ∗ L\subseteq\Sigma^* L ⊆ Σ ∗ Finite Automata (DFA NFA) — machines that decide membership in a language.Regular Expressions — algebra built on ∪ \cup ∪ ∗ * ∗ Σ \Sigma Σ Context-Free Grammars — generate languages beyond regular.Countability and Diophantine Diagonalization — why 2 Σ ∗ 2^{\Sigma^*} 2 Σ ∗ Pumping Lemma — uses string length & concatenation structure proved here.
Intuition Hinglish mein samjhoDekho, Theory of Computation ki saari building teen floor par khadi hai: Alphabet, String, Language . Alphabet matlab Σ \Sigma Σ finite aur non-empty set of symbols, jaise { 0 , 1 } \{0,1\} { 0 , 1 } 0110. Aur ek special string hoti hai ε \varepsilon ε 0 0 0 set — yaani L ⊆ Σ ∗ L\subseteq\Sigma^* L ⊆ Σ ∗
Sabse zyada confusion teen cheezon mein hoti hai: ε \varepsilon ε { ε } \{\varepsilon\} { ε } ∅ \varnothing ∅ ∅ \varnothing ∅ khaali dabba hai (0 strings), { ε } \{\varepsilon\} { ε } ek blank kaagaz pada hai (1 string), aur ε \varepsilon ε wo blank kaagaz hai (ek string). Inko same samajhna sabse common galti hai exam mein.
Counting ka logic simple: length k k k ∣ Σ ∣ |\Sigma| ∣Σ∣ k k k ∣ Σ ∣ k |\Sigma|^k ∣Σ ∣ k 2 3 = 8 2^3=8 2 3 = 8 Σ ∗ \Sigma^* Σ ∗ countable hai, kyunki saari strings finite-length hain — length ke order mein list kar sakte ho.
Ye foundation kyun matter karta hai? Aage jo bhi padhoge — DFA, NFA, regex, grammar, Turing machine — har machine basically ek hi sawaal puchhti hai: "Kya ye string is language ke club mein allowed hai ya nahi?" Toh agar alphabet-string-language clear hai, toh poora ToC chapter butter ki tarah smooth chalega.
