Finite automaton আর regular expression-এর পরিচয়

১ · DFA — সসীম স্মৃতির একটি যন্ত্র

পর্ব ১২-এ alphabet Σ, string, empty string ε আর Σ* সংজ্ঞায়িত করেছি; Σ*-এর যেকোনো subset একটি formal language. পর্ব ৭৩ “Grammar আর formal language — BNF থেকে Chomsky-র শ্রেণি” ভাষা তৈরি করার নিয়ম দেখায় (grammar). এই পর্বের প্রশ্ন উল্টো: একটি string দেখে কোনো যন্ত্র কি বলতে পারে সেটি ভাষায় আছে কি না, আর যন্ত্রের স্মৃতি সসীম হলে কোন ভাষা চেনা যায়।

δ একবারে একটি চিহ্ন সামলায়। পুরো string-এর জন্য তাকে পর্ব ১২-এর ধাঁচে recursive সংজ্ঞায় বাড়ানো হয়।

প্রথম উদাহরণ: Σ = {0, 1}-এ “1-এর সংখ্যা জোড়”। দুটি state যথেষ্ট: E (এ পর্যন্ত জোড় সংখ্যক 1) আর O (বিজোড়)। 0 পড়লে state বদলায় না, 1 পড়লে E আর O অদলবদল হয়; q₀ = E, F = {E}. পুরো ইতিহাস নয়, শুধু একটি parity বিট মনে রাখলেই চলে, ঠিক পর্ব ৬৯-এর XOR-এর মতো।

দ্বিতীয় উদাহরণ বাজারঘর থেকে। ধরি (কাল্পনিক নিয়ম) বৈধ অর্ডার-কোড হলো অঙ্কের যেকোনো string, যার শেষ দুই অঙ্ক “25”, যেমন 40125. DFA-র state মনে রাখে “25”-এর কতটুকু এইমাত্র মিলেছে: 0 (কিছুই না), 1 (শেষে একটি 2), 2 (শেষে 25, accepting). যেকোনো state থেকে 2 পড়লে state 1; state 1-এ 5 পড়লে state 2; বাকি সব অঙ্কে state 0. দশটি অঙ্ক আর তিনটি state মিলে টেবিলে ৩০টি ঘর, কিন্তু নিয়ম মাত্র তিন লাইনের। সংজ্ঞা অনুযায়ী δ প্রতিটি ঘরে সংজ্ঞায়িত; কোনো ঘরে “এখানে আর আশা নেই” বোঝাতে চাইলে একটি dead state রাখা হয়, যেখান থেকে প্রতিটি চিহ্নে নিজের কাছেই ফেরা, আর যা accepting নয়। যেমন কোড যদি অবশ্যই অক্ষর B দিয়ে শুরু হতে হয়, তবে প্রথম চিহ্ন অন্য কিছু হলে যন্ত্র dead state-এ চলে যায়, আর কখনো বের হয় না।

তৃতীয় উদাহরণটিই এই পর্বের প্রধান চরিত্র: binary string-কে সংখ্যা হিসেবে পড়ে বলা, সেটি ৩ দিয়ে বিভাজ্য কি না। State 0, 1, 2; δ(q, b) = (2q + b) mod 3; q₀ = 0, F = {0}. নিচের transition diagram-এ বৃত্ত হলো state, তীর হলো transition, দুই দাগের বৃত্ত accepting.

২ · Invariant দিয়ে সঠিকতার প্রমাণ — ৩ দিয়ে বিভাজ্যতা

“যন্ত্রটি ঠিক কাজ করে” দাবিটি প্রমাণ করতে পর্ব ১৩-এর loop invariant-এর ধারণাই কাজে লাগে: প্রতিটি চিহ্ন পড়ার পর একটি বক্তব্য সত্য থাকে। Binary string w-এর মান val(w) recursive: val(ε) = 0, val(wb) = 2 · val(w) + b (একটি বিট ডানে যোগ করা মানে দ্বিগুণ করে সেই বিট যোগ)।

1. Base: w = ε. δ*(0, ε) = 0 = val(ε) mod 3. — δ*-এর সংজ্ঞা
2. Inductive hypothesis: কোনো w-এর জন্য δ*(0, w) = val(w) mod 3 = r. — induction, |w|-এর ওপর
3. Step: δ*(0, wb) = δ(r, b) = (2r + b) mod 3. — δ*-এর সংজ্ঞা আর DFA-র নিয়ম
4. r ≡ val(w) (mod 3), তাই 2r + b ≡ 2 · val(w) + b = val(wb) (mod 3); দুটির ভাগশেষ সমান। — পর্ব ২২-এর congruence-এর যোগ ও গুণ
5. অতএব δ*(0, wb) = val(wb) mod 3, আর F = {0} বলে গ্রহণ ⇔ ভাগশেষ 0. ∎

একই যুক্তিতে যেকোনো m-এর জন্য m-টি state-এর DFA “m দিয়ে বিভাজ্য” চেনে: δ(q, b) = (2q + b) mod m. দশমিক অঙ্কের জন্য নিয়মটি δ(q, d) = (10q + d) mod m. m = 3-এ 10 ≡ 1 (mod 3), তাই নিয়ম দাঁড়ায় δ(q, d) = (q + d) mod 3: যন্ত্রটি আসলে অঙ্কগুলোর যোগফলের ভাগশেষ রাখছে। স্কুলের “অঙ্কের যোগফল ৩ দিয়ে বিভাজ্য হলে সংখ্যাটিও” নিয়মটি এই DFA-র সঠিকতারই আরেক রূপ। নিচের stepper 10110 (= 22) নিয়ে যন্ত্রটি চালায়।

1q = q0 (start)2read 1: (2·0+1) mod 33read 0: (2·1+0) mod 34read 1: (2·2+1) mod 35read 1: (2·2+1) mod 36read 0: (2·2+0) mod 37q1 ∉ F → reject

প্রমাণ থাকলেও ছোট ক্ষেত্রে পূর্ণ গণনা ভুল ধরার সবচেয়ে সস্তা উপায়। নিচের ব্লক একটি সাধারণ DFA-চালক লেখে, তারপর দৈর্ঘ্য 0 থেকে 12-এর সব binary string-এ mod-3 DFA-কে Python-এর নিজের ভাগশেষের সঙ্গে মেলায়, আর জোড়-1 ও অর্ডার-কোডের DFA-ও চালায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def run(delta, start, accept, w):
    q, path = start, [start]
    for ch in w:                         # one table lookup per symbol
        q = delta[q, ch]
        path.append(q)
    return q in accept, path
# mod-3 DFA: the state is (value of the bits read so far) mod 3
MOD3 = {(q, b): (2 * q + int(b)) % 3 for q in range(3) for b in "01"}
print("10110 =", int("10110", 2), "->", run(MOD3, 0, {0}, "10110"))
total = bad = 0
for n in range(13):                      # every binary string of length 0..12
    for w in map("".join, product("01", repeat=n)):
        value = int(w, 2) if w else 0
        total += 1
        bad += run(MOD3, 0, {0}, w)[0] != (value % 3 == 0)
print("mod-3 DFA: strings checked", total, "disagreements", bad)
EVEN = {("E", "0"): "E", ("E", "1"): "O", ("O", "0"): "O", ("O", "1"): "E"}
print("even 1s:", [w for w in ("", "1", "11", "1011", "0110") if run(EVEN, "E", {"E"}, w)[0]])
def step25(q, ch):                       # how much of the tail "25" is matched
    if ch == "2":
        return 1
    return 2 if (ch == "5" and q == 1) else 0
D25 = {(q, c): step25(q, c) for q in range(3) for c in "0123456789"}
print({x: run(D25, 0, {2}, x)[0] for x in ("40125", "4012", "2525", "252")})
ok = all(run(D25, 0, {2}, w)[0] == w.endswith("25")
         for n in range(5) for w in map("".join, product("0123456789", repeat=n)))
print("order-code DFA agrees with endswith('25') on 11111 strings:", ok)

10110 = 22 -> (False, [0, 1, 2, 2, 2, 1])
mod-3 DFA: strings checked 8191 disagreements 0
even 1s: ['', '11', '0110']
{'40125': True, '4012': False, '2525': True, '252': False}
order-code DFA agrees with endswith('25') on 11111 strings: True

৩ · NFA আর ε-move — অনুমান করতে পারা যন্ত্র

ভাষা L₃ = {w ∈ {0, 1}* : শেষ থেকে তৃতীয় চিহ্ন 1}. DFA বানাতে গেলে সব সময় শেষ তিনটি বিট মনে রাখতে হয়। কিন্তু একটি “অনুমান করতে পারা” যন্ত্র সহজে বলা যায়: পড়তে থাকুন; কোনো 1 দেখে অনুমান করুন “এটিই শেষ থেকে তৃতীয়”, তারপর ঠিক আরও দুটি চিহ্ন পড়ে থামুন। অনুমান ঠিক হলে কোনো একটি পথ accepting state-এ পৌঁছায়।

NFA চালানোর হিসাব হলো “এই মুহূর্তে যেসব state-এ থাকা সম্ভব”, তার সেট। ε-move থাকলে প্রতিটি ধাপের পরে সেটটিকে বড় করতে হয়: q-এর ε-closure E(q) মানে q থেকে শুধু ε-তীর ধরে যত state-এ যাওয়া যায় (q নিজেও)। এটি ঠিক “ε-তীর” relation-এর reflexive-transitive closure, যা পর্ব ৫৪-এ Warshall দিয়ে গুনেছেন। ε-move কোথায় কাজে লাগে? ধরুন N₁ আর N₂ দুটি NFA. একটি নতুন শুরুর state থেকে দুই যন্ত্রের শুরুতে দুটি ε-তীর দিলেই L(N₁) ∪ L(N₂)-এর NFA তৈরি: যন্ত্র কোনো চিহ্ন না পড়েই “কোন যন্ত্র চালাব” অনুমান করে নেয়। §৫-এর Thompson-এর নির্মাণ এই কৌশলই বারবার ব্যবহার করে। ছবির NFA-তে 0110 পড়লে সম্ভাব্য সেট {q0} → {q0} → {q0, q1} → {q0, q1, q2} → {q0, q2, q3}; শেষ সেটে q3 আছে, তাই গ্রহণ (শেষ থেকে তৃতীয় চিহ্ন 1).

৪ · Subset construction — NFA থেকে DFA

আগের অনুচ্ছেদের “সম্ভাব্য state-এর সেট” নিজেই একটি DFA-র state হতে পারে। Michael Rabin আর Dana Scott ১৯৫৯ সালের প্রবন্ধে এই subset construction দেন।

প্রমাণ (সরলতার জন্য ε-move ছাড়া; তখন E(S) = S, আর ε থাকলে প্রতিটি ধাপে E বসালে একই যুক্তি চলে)। NFA-র জন্য δ_N*(q₀, w) মানে w পড়ার পর সম্ভাব্য সব state-এর সেট: δ_N*(q₀, ε) = {q₀}, δ_N*(q₀, va) = ⋃_{s ∈ δN*(q0, v)} δ(s, a).

1. দাবি: সব w-এর জন্য δ_D*({q₀}, w) = δ_N*(q₀, w). |w|-এর ওপর induction. — structural induction
2. Base: w = ε হলে দুই দিকই {q₀}. — দুই δ*-এর সংজ্ঞা
3. Step: w = va. δ_D*({q₀}, va) = δ_D(δ_D*({q₀}, v), a) = δ_D(δ_N*(q₀, v), a) = ⋃_{s ∈ δN*(q0, v)} δ(s, a) = δ_N*(q₀, va). — hypothesis, তারপর δ_D-এর সংজ্ঞা
4. D w গ্রহণ করে ⇔ δ_D*({q₀}, w) ∩ F ≠ ∅ ⇔ N-এর অন্তত একটি পথ F-এ শেষ হয় ⇔ N w গ্রহণ করে। ∎

বাস্তবে সব 2^|Q|টি subset লেখা হয় না; শুরু থেকে যেগুলোতে পৌঁছানো যায়, শুধু সেগুলো ধাপে ধাপে বের করা হয়। ছবির NFA-তে (state-কে 0, 1, 2, 3 লিখে):

1start = {0}2{0}: 0→{0} 1→{01}3{01}: 0→{02} 1→{012}4{02}: 0→{03} 1→{013}5{012}: 0→{023} 1→{0123}64 more rows: nothing new

লক্ষ করুন, i ∈ S ঠিক তখন, যখন শেষ থেকে i-তম চিহ্ন 1 (i = 1, 2, 3). অর্থাৎ DFA শেষ তিনটি বিট মনে রাখছে, আর তার 2³ = 8 রকম সম্ভাবনা। এটা কি এড়ানো যায়? না।

1. দৈর্ঘ্য n-এর 2ⁿটি string নিন। ধরুন কোনো DFA-তে state 2ⁿ-এর কম। তাহলে দুটি আলাদা string u ≠ v আছে, যারা শুরু থেকে একই state-এ পৌঁছায়। — পর্ব ৩২-এর pigeonhole
2. u আর v কোনো অবস্থান i-তে আলাদা (1 ≤ i ≤ n); ধরি u_i = 1, v_i = 0. z = 0ⁱ⁻¹ যোগ করুন। uz আর vz-এর দৈর্ঘ্য n + i − 1, আর শেষ থেকে n-তম চিহ্ন ঠিক অবস্থান i-এর চিহ্ন। — গণনা
3. তাই uz ∈ L_n, vz ∉ L_n. কিন্তু একই state থেকে একই z পড়লে DFA একই state-এ পৌঁছায়, তাই দুটিকে একই সিদ্ধান্ত দেয়। বিরোধ। ∎

এমন u, v-কে বলে distinguishable: কোনো z আছে, যা জুড়লে একটি ভাষায় ঢোকে আর অন্যটি ঢোকে না। এই ধারণাই §৮-এর Myhill–Nerode. নিচের ব্লক subset construction চালায়, টেবিল ছাপায়, দৈর্ঘ্য 10 পর্যন্ত সব string-এ ভাষা মেলায়, আর n = 1 থেকে 8-এ পৌঁছানো DFA state গোনে।

from itertools import product
def nfa_move(S, a, n):                   # NFA: "n-th symbol from the end is 1"
    out = set()
    for s in S:
        if s == 0:
            out.add(0)                   # state 0 keeps guessing "not yet"
            if a == "1":
                out.add(1)               # ... or guesses "this 1 is the one"
        elif s < n:
            out.add(s + 1)               # count the symbols after the guess
    return frozenset(out)
def subset_construction(n):
    start = frozenset({0})
    dfa, todo = {}, [start]
    while todo:                          # only the reachable subsets
        S = todo.pop(0)
        if S not in dfa:
            dfa[S] = {a: nfa_move(S, a, n) for a in "01"}
            todo += dfa[S].values()
    return start, dfa
start, dfa = subset_construction(3)
for S, row in dfa.items():
    print(sorted(S), "0->", sorted(row["0"]), "1->", sorted(row["1"]), "*" if 3 in S else "")
def accepts(w):
    S = start
    for a in w:
        S = dfa[S][a]
    return 3 in S
bad = sum(accepts(w) != (len(w) >= 3 and w[-3] == "1")
          for k in range(11) for w in map("".join, product("01", repeat=k)))
print("n=3: DFA states", len(dfa), "| strings up to length 10:", 2**11 - 1, "disagreements", bad)
print("n -> reachable DFA states:", {n: len(subset_construction(n)[1]) for n in range(1, 9)})

[0] 0-> [0] 1-> [0, 1]
[0, 1] 0-> [0, 2] 1-> [0, 1, 2]
[0, 2] 0-> [0, 3] 1-> [0, 1, 3]
[0, 1, 2] 0-> [0, 2, 3] 1-> [0, 1, 2, 3]
[0, 3] 0-> [0] 1-> [0, 1] *
[0, 1, 3] 0-> [0, 2] 1-> [0, 1, 2] *
[0, 2, 3] 0-> [0, 3] 1-> [0, 1, 3] *
[0, 1, 2, 3] 0-> [0, 2, 3] 1-> [0, 1, 2, 3] *
n=3: DFA states 8 | strings up to length 10: 2047 disagreements 0
n -> reachable DFA states: {1: 2, 2: 4, 3: 8, 4: 16, 5: 32, 6: 64, 7: 128, 8: 256}

৫ · Regular expression আর Kleene-এর উপপাদ্য

যন্ত্রের বদলে একটি সূত্র দিয়েও ভাষা লেখা যায়। ভাষার তিনটি operation (পর্ব ৭৩-এর বিষয়, star-এর সংজ্ঞা পর্ব ১২-এ): union L ∪ K, concatenation LK = {xy : x ∈ L, y ∈ K}, আর Kleene star L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ⋯ . Regular expression ঠিক এই তিনটি দিয়ে গড়া।

উদাহরণ: (0 | 1)*1(0 | 1)(0 | 1) হলো L₃; বাজারঘরের অর্ডার-কোড (0 | 1 | ⋯ | 9)*25; আর জোড় সংখ্যক 1: 0*(10*10*)*. শেষটি যাচাই করতে লক্ষ করুন, প্রতিটি 10*10* ব্লক ঠিক দুটি 1 আনে।

NFA ⇒ DFA হলো উপপাদ্য ৪.১, আর DFA নিজেই একটি NFA. Regex ⇒ NFA নিচের নির্মাণ দেখায়। NFA ⇒ regex-এর প্রমাণ এখানে বাদ রাখছি: Kleene-এর মূল পদ্ধতিতে R_ij^(k) = “i থেকে j-তে, মাঝে শুধু 1..k নম্বর state ব্যবহার করে” পথের regex, k এক এক করে বাড়িয়ে গোনা হয়, ঠিক Warshall-এর algorithm-এর কাঠামো (পর্ব ৫৪)। এর পূর্ণ রূপ পরিকল্পিত Theory of Computation কোর্সের বিষয়; এই পর্ব discrete math-এর দিক থেকে পরিচয় মাত্র।

Regex থেকে NFA: Thompson-এর নির্মাণ

Ken Thompson ১৯৬৮ সালের প্রবন্ধে regex-কে সরাসরি NFA-তে রূপ দেওয়ার পদ্ধতি দেন। প্রতিটি টুকরার NFA-র ঠিক একটি শুরু আর একটি শেষ (accepting) state থাকে; regex-এর গঠনের ওপর structural induction:

প্রতিটি নিয়মে নতুন NFA-র ভাষা ঠিক সংজ্ঞা ৫.১-এর ভাষা (যেমন R*-এ পথটি R-এর NFA-কে শূন্য বা তার বেশি বার পার হয়)। প্রতিটি চিহ্ন বা operator বড়জোর ২টি state যোগ করে, তাই regex-এর দৈর্ঘ্য m হলে NFA-তে বড়জোর 2m state. যেমন (0 | 1)*1: 2 + 2 + 2 = 6, star-এ 8, শেষে “1”-এর 2 জুড়ে মোট 10 (scratch-এ গোনা)।

বাস্তবের regex

Python-এর re module-এ (Python কোর্সের পর্ব ৩০) \d*25, [A-Z]{2}\d{3}-এর মতো সংক্ষেপ আছে; এগুলো ওপরের তিনটি operation-এর সংক্ষিপ্ত রূপ মাত্র, যেমন \d = (0 | ⋯ | 9). কিন্তু দুটি সতর্কতা। প্রথমত, backreference (\1 = “আগে যা মিলেছে, হুবহু আবার”) গাণিতিক অর্থে regular নয়; §৭-এর ব্লকে দেখবেন (a*)b\1 ভাষা aⁿbaⁿ চেনে, যা regular নয়। দ্বিতীয়ত, অনেক engine NFA-র পথগুলো একটি একটি করে চেষ্টা করে (backtracking); কিছু pattern-এ, যেমন (a+)+b, মিল না পেলে চেষ্টার সংখ্যা ইনপুটের দৈর্ঘ্যের সঙ্গে ঘাতের হারে বাড়তে পারে বলে বহুল নথিভুক্ত (catastrophic backtracking). Subset construction-এর মতো একসঙ্গে সব state রাখার পদ্ধতি এই বিস্ফোরণ এড়ায়।

৬ · Closure property — product construction আর complement

Regular language-এর শ্রেণি কোন operation-এ বদ্ধ? Union, concatenation আর star-এ বদ্ধতা Kleene থেকে সরাসরি আসে। Intersection আর complement-এর জন্য সুন্দর সরাসরি নির্মাণ আছে।

1. Lemma: সব w-এর জন্য δ*((p, q), w) = (δ₁*(p, w), δ₂*(q, w)). w = ε-তে দুই দিকই (p, q). — base
2. w = va হলে δ*((p, q), va) = δ((δ₁*(p, v), δ₂*(q, v)), a) = (δ₁*(p, va), δ₂*(q, va)). — hypothesis, δ-এর সংজ্ঞা
3. অতএব w ∈ L(M) ⇔ (δ₁*(s₁, w), δ₂*(s₂, w)) ∈ F₁ × F₂ ⇔ দুই যন্ত্রই w গ্রহণ করে ⇔ w ∈ L(M₁) ∩ L(M₂). ∎ — পর্ব ১৪-এর Cartesian product

দুই যন্ত্র পাশাপাশি চলছে, যেন দুজন পরীক্ষক একই খাতা একসঙ্গে পড়ছেন আর নিজের নিজের নম্বর রাখছেন। State-সংখ্যা |Q₁| · |Q₂|, গুণের নিয়ম।

বাজারঘরের উদাহরণ: ধরুন একটি বিশেষ অফারের কোড হতে হবে “শেষে 25” এবং সংখ্যাটি ৩ দিয়ে বিভাজ্য। প্রথম শর্তের DFA-তে ৩টি state (§১), দ্বিতীয়টির δ(q, d) = (q + d) mod 3-এও ৩টি, তাই product-এ 3 × 3 = 9টি state, আর accepting শুধু (2, 0): “25 মিলেছে, ভাগশেষ 0”. তিন অঙ্কের কোডের মধ্যে এমন কোড 225, 525 আর 825: d25-এর অঙ্কের যোগফল d + 7, যা ৩ দিয়ে বিভাজ্য ঠিক d = 2, 5, 8-এ (scratch-এ মেলানো)। আলাদা আলাদা দুটি ছোট যন্ত্র লিখে product নেওয়া একটি বড় যন্ত্র সরাসরি আঁকার চেয়ে অনেক কম ভুলপ্রবণ।

প্রমাণ: δ বদলায়নি, তাই δ*(q₀, w) দুই যন্ত্রে একই state. w ∈ L(M′) ⇔ সেই state ∈ Q ∖ F ⇔ সেটি F-এ নেই ⇔ w ∉ L(M). ∎ এখানে দুটি শর্ত জরুরি: যন্ত্রটি deterministic, আর প্রতিটি ঘরে একটি transition আছে (না থাকলে একটি “ডাস্টবিন” state যোগ করে পূরণ করতে হয়)। NFA-তে accepting state উল্টালে কাজ হয় না (অনুশীলন ৪)। ফলাফল: L₁ ∖ L₂ = L₁ ∩ (Σ* ∖ L₂)-ও regular, আর “দুটি DFA-র ভাষা সমান কি না” প্রশ্নটি বোঝা যায়: symmetric difference খালি কি না দেখলেই হয়।

৭ · Pumping lemma — যা DFA পারে না

aⁿbⁿ (n ≥ 0) চিনতে কয়টি a পড়া হলো তা গুনে রাখতে হয়, আর n যত খুশি বড় হতে পারে। সসীম state দিয়ে এটি অসম্ভব মনে হয়; সেই অনুভূতিকে প্রমাণে বদলানোর হাতিয়ার pumping lemma, যার প্রথম প্রকাশ সাধারণত Bar-Hillel, Perles আর Shamir-এর ১৯৬১ সালের প্রবন্ধকে ধরা হয়।

1. L-এর একটি DFA M নিন, আর p = M-এর state-সংখ্যা। — regular-এর সংজ্ঞা
2. s = s₁s₂⋯s_n ∈ L, n ≥ p. M-এর পথ r₀ = q₀, r_k = δ(r_k−1, s_k); r_n ∈ F, কারণ s ∈ L. — δ*
3. প্রথম p + 1টি state r₀, …, r_p; কিন্তু state মাত্র p-টি, তাই কোনো j < k ≤ p-তে r_j = r_k. — পর্ব ৩২-এর pigeonhole
4. x = s₁⋯s_j, y = s_j+1⋯s_k, z = s_k+1⋯s_n. তাহলে |xy| = k ≤ p আর |y| = k − j ≥ 1. — (ক), (খ)
5. δ*(r_j, y) = r_k = r_j: y পড়ে যন্ত্র একই state-এ ফেরে, তাই i ≥ 0 সংখ্যক y পড়লেও r_j-তে থাকে (i-এর ওপর induction). ফলে δ*(q₀, xyⁱz) = δ*(r_j, z) = r_n ∈ F. ∎ — (গ)

Lemma-টি regular হওয়ার প্রয়োজনীয় শর্ত, যথেষ্ট নয়: কিছু non-regular ভাষাও এটি মানে। তাই এটি দিয়ে শুধু “regular নয়” প্রমাণ করা যায়, contradiction দিয়ে। আর quantifier-এর ক্রম (পর্ব ৫) মনে রাখুন: ∃p ∀s ∃(x, y, z) ∀i. প্রমাণকারী s বাছেন, কিন্তু বিভাজন বাছে প্রতিপক্ষ, তাই প্রতিটি বিভাজনকে হারাতে হয়।

1assume L regular, p2choose s = a^p b^p3any split: |xy|≤p, |y|≥14so y = a^k, 1 ≤ k ≤ p5pump i = 0: x z6a^(p−k) b^p ∉ L ⇒ ⊥

নিচের ব্লক একই যুক্তি ছোট p-তে পূর্ণ গণনায় দেখে: a^pb^p-এর প্রতিটি বৈধ বিভাজন চেষ্টা করে, i = 0..3-এ সব xyⁱz ভাষায় থাকে এমন “ভালো” বিভাজন খোঁজে। তুলনার জন্য জোড়-1-এর ভাষায় (DFA-তে ২ state, তাই p = 2) প্রতিটি সদস্যের ভালো বিভাজন মেলে কি না দেখে, আর Python-এর backreference পরীক্ষা করে।

import re
from itertools import product
def in_anbn(s):
    k = len(s) // 2
    return s == "a" * k + "b" * k
def even_ones(s):
    return s.count("1") % 2 == 0
def good_split(s, p, member):
    # a split s = xyz with |xy| <= p, |y| >= 1 and xy^i z in L for i = 0..3
    for j in range(1, p + 1):            # j = |xy|
        for k in range(1, j + 1):        # k = |y|
            x, y, z = s[:j - k], s[j - k:j], s[j:]
            if all(member(x + y * i + z) for i in range(4)):
                return (x, y, z)
    return None
for p in range(1, 8):
    s = "a" * p + "b" * p
    print("p =", p, s, "-> good split:", good_split(s, p, in_anbn))
tested = [w for n in range(2, 11)
          for w in map("".join, product("01", repeat=n)) if even_ones(w)]
print("even 1s, p = 2: every member of length 2..10 has a good split:",
      all(good_split(w, 2, even_ones) for w in tested), len(tested))
print("example:", good_split("1001", 2, even_ones))
pat = re.compile(r"(a*)b\1")             # backreference \1 = "the same a's again"
print("re with backreference accepts:",
      [w for w in ("aba", "aabaa", "aaba", "b", "abaa") if pat.fullmatch(w)])

p = 1 ab -> good split: None
p = 2 aabb -> good split: None
p = 3 aaabbb -> good split: None
p = 4 aaaabbbb -> good split: None
p = 5 aaaaabbbbb -> good split: None
p = 6 aaaaaabbbbbb -> good split: None
p = 7 aaaaaaabbbbbbb -> good split: None
even 1s, p = 2: every member of length 2..10 has a good split: True 1022
example: ('1', '0', '01')
re with backreference accepts: ['aba', 'aabaa', 'b']

৮ · Myhill–Nerode, minimisation আর output-ওয়ালা যন্ত্র

একই ভাষার অনেক DFA হয়। সবচেয়ে ছোটটি কত বড়, আর সেটি কি অনন্য? উত্তর আসে পর্ব ৫৫-এর equivalence relation থেকে। ভাষা L-এর জন্য Σ*-এ সংজ্ঞায়িত করুন: x ≡_L y ⇔ সব z ∈ Σ*-এর জন্য (xz ∈ L ⇔ yz ∈ L). অর্থাৎ x আর y-কে কোনো ভবিষ্যৎ দিয়ে আলাদা করা যায় না (§৪-এর distinguishable-এর উল্টো)। এটি reflexive, symmetric আর transitive, তাই Σ*-কে equivalence class-এ ভাগ করে।

এক দিক সহজ: DFA-তে একই state-এ পৌঁছানো দুটি string ≡_L-এ সম্পর্কিত, তাই class-সংখ্যা ≤ state-সংখ্যা; উপপাদ্য ৪.২-এর যুক্তি ঠিক এটাই। aⁿbⁿ-এর জন্য a, aa, aaa, … পরস্পর distinguishable (aⁱ আর a^j-কে z = bⁱ আলাদা করে), তাই অসীম class: pumping ছাড়াই দ্বিতীয় একটি প্রমাণ। Myhill (১৯৫৭) আর Nerode (১৯৫৮)-এর নামে উপপাদ্যটি; বিস্তারিত পরিকল্পিত Theory of Computation কোর্সে।

DFA minimisation: partition refinement

একটি DFA দেওয়া থাকলে সমতুল্য state-গুলো জোড়া লাগিয়ে সবচেয়ে ছোট DFA পাওয়া যায়। শুরুর ভাগ: {accepting}, {non-accepting}. প্রতি round-এ একটি ব্লকের দুটি state-কে আলাদা করুন, যদি কোনো চিহ্নে তারা এখনকার ভাগের আলাদা ব্লকে যায়। ভাগ আর না বদলালে থামুন; প্রতিটি ব্লক একটি নতুন state. প্রতি round-এ ব্লক বাড়ে বা algorithm থামে, তাই বড়জোর |Q| round. আলাদা ব্লকের state-গুলো সত্যিই distinguishable (কোন চিহ্নে ভাগ হলো, সেটি ধরে উল্টো দিকে একটি আলাদা-করা z বানানো যায়), আর শেষ ভাগের একই ব্লকের state-গুলো কোনো z-তে আলাদা হয় না; তাই ফলাফল উপপাদ্য ৮.১-এর অনন্য DFA.

উদাহরণ: “binary মান mod 6” DFA, state 0..5, δ(q, b) = (2q + b) mod 6, accepting {0, 3} (৩ দিয়ে বিভাজ্য)। শুরুর ভাগ {0, 3} | {1, 2, 4, 5}. State 1 আর 4 দুটিই 1 পড়লে accepting ব্লকে যায় (3), কিন্তু 2 আর 5 যায় না (5): ভাগ {0, 3} | {1, 4} | {2, 5}. পরের round-এ কিছু বদলায় না। তিনটি ব্লক ঠিক mod-3-এর তিনটি ভাগশেষ: q আর q + 3 একই। নিচের ব্লক product construction আর এই minimisation দুটিই চালিয়ে পূর্ণ গণনায় মেলায়।

from itertools import product
def run(delta, q, w):
    for a in w:
        q = delta[q, a]
    return q
EVEN = {("E", "0"): "E", ("E", "1"): "O", ("O", "0"): "O", ("O", "1"): "E"}
MOD3 = {(q, b): (2 * q + int(b)) % 3 for q in range(3) for b in "01"}
# product construction: run both machines side by side on pairs of states
PROD = {((p, q), a): (EVEN[p, a], MOD3[q, a]) for p in "EO" for q in range(3) for a in "01"}
words = [w for n in range(11) for w in map("".join, product("01", repeat=n))]
bad = sum((run(PROD, ("E", 0), w) == ("E", 0)) !=
          (w.count("1") % 2 == 0 and (int(w, 2) if w else 0) % 3 == 0) for w in words)
print("product DFA:", len({k[0] for k in PROD}), "states; disagreements on", len(words), "strings:", bad)
# minimisation: DFA for (value mod 6), accepting 0 and 3 ("divisible by 3")
M6 = {(q, b): (2 * q + int(b)) % 6 for q in range(6) for b in "01"}
P = [{0, 3}, {1, 2, 4, 5}]                # round 0: accepting | non-accepting
while True:
    where = {x: i for i, B in enumerate(P) for x in B}
    newP = []
    for B in P:                          # split B by (block after 0, block after 1)
        groups = {}
        for x in sorted(B):
            groups.setdefault((where[M6[x, "0"]], where[M6[x, "1"]]), set()).add(x)
        newP += groups.values()
    print("blocks:", [sorted(B) for B in newP])
    if len(newP) == len(P):
        break
    P = newP
where = {x: i for i, B in enumerate(P) for x in B}
MIN = {(i, a): where[M6[min(B), a]] for i, B in enumerate(P) for a in "01"}
same = all((run(M6, 0, w) in (0, 3)) == (run(MIN, where[0], w) == where[0]) for w in words)
print("minimal DFA has", len(P), "states; same language up to length 10:", same)

product DFA: 6 states; disagreements on 2047 strings: 0
blocks: [[0, 3], [1, 4], [2, 5]]
blocks: [[0, 3], [1, 4], [2, 5]]
minimal DFA has 3 states; same language up to length 10: True

Output-ওয়ালা যন্ত্র: বাজারঘরের checkout

DFA শুধু হ্যাঁ/না বলে। বাস্তবের অনেক যন্ত্র প্রতিটি ধাপে কিছু করে: পর্দা দেখায়, বার্তা পাঠায়। Moore machine-এ output শুধু state-এর ওপর নির্ভর করে, Mealy machine-এ state আর input দুটির ওপর। বাজারঘরের checkout (কাল্পনিক নকশা):

“নিশ্চিত” থেকে কোনো তীর বের হয় না, তাই একটি অর্ডার দুবার নিশ্চিত হতে পারে না: এমন নিরাপত্তা-দাবি state-এর সসীম গ্রাফে reachability দেখেই যাচাই করা যায় (পর্ব ৫৯-এর path), যা model checking-এর মূল ধারণা। Hardware-এ এর রূপায়ণ Computer Architecture কোর্সের পর্ব ১৭-এ।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: গণনা

(ক) দৈর্ঘ্য ঠিক 6-এর কয়টি binary string (শুরুতে 0 চলবে) mod-3 DFA গ্রহণ করে? (খ) দৈর্ঘ্য 5-এর কয়টি string-এ শেষ থেকে তৃতীয় চিহ্ন 1? (গ) বাজারঘরের কুপন-কোড [A-Z]{2}[0-9]{3} (দুটি বড় হাতের ইংরেজি অক্ষর, তারপর তিনটি অঙ্ক) কয়টি?

1. (ক) দৈর্ঘ্য 6-এর string মানে 0 থেকে 63-এর সংখ্যা; ৩-এর গুণিতক 0, 3, …, 63, মোট 63/3 + 1 = 22.
2. (খ) শেষ থেকে তৃতীয় অবস্থান 1-এ বাঁধা, বাকি ৪টি অবস্থান মুক্ত: 2⁴ = 16.
3. (গ) গুণের নিয়ম (পর্ব ৩১): 26² × 10³ = 676,000. (তিনটিই scratch-এ গোনা।)

অঙ্ক ২: subset construction

Σ = {a, b}-এ NFA: state 0 (শুরু), 1, 2 (accepting); 0-তে a, b-এ নিজের কাছে ফেরা, 0 থেকে a-তে 1, 1 থেকে b-তে 2. ভাষা: “ab দিয়ে শেষ”। DFA বানান।

1. {0}: a → {0, 1}, b → {0}.
2. {0, 1}: a → {0, 1}, b → {0, 2}.
3. {0, 2}: a → {0, 1}, b → {0}. নতুন কিছু নেই: ৩টি state, accepting শুধু {0, 2}. সম্ভাব্য 2³ = 8টির মধ্যে মাত্র ৩টিতে পৌঁছানো যায়।

অঙ্ক ৩: সবচেয়ে ছোট DFA

L₅ (শেষ থেকে পঞ্চম চিহ্ন 1)-এর সবচেয়ে ছোট DFA-তে কয়টি state? উত্তর: উপপাদ্য ৪.২ অনুযায়ী অন্তত 2⁵, আর subset construction ঠিক 32টি দেয় (§৪-এর কোড), তাই 32. Thompson-এর নিয়মে (0 | 1)*1-এর NFA-তে 10টি state (§৫)।

অঙ্ক ৪: DFA দিয়ে গোনা

দৈর্ঘ্য n-এর কয়টি binary string-এ পরপর দুটি 1 নেই (যেমন বাজারঘরের একটি কাল্পনিক নিয়ম: পরপর দুই দিন ছুটির দিন নয়)? DFA: A = “শেষ চিহ্ন 1 নয়” (শুরুও এখানে), B = “শেষ চিহ্ন 1”, আর dead state D. A-তে 0 → A, 1 → B; B-তে 0 → A, 1 → D. A আর B accepting.

1. a_n, b_n = দৈর্ঘ্য n-এর যেসব string যথাক্রমে A আর B-তে শেষ হয়। A-তে আসা যায় A বা B থেকে 0 পড়ে, B-তে শুধু A থেকে 1 পড়ে: a_n+1 = a_n + b_n, b_n+1 = a_n. — যোগের নিয়ম
2. শুরু a₀ = 1, b₀ = 0. মোট t_n = a_n + b_n = a_n+1, আর a_n+2 = a_n+1 + a_n: Fibonacci-র recurrence (পর্ব ৪৫)।
3. t₃ = 5, t₄ = 8, t₅ = 13, t₁₀ = 144 (scratch-এ সব string গুনে মেলানো)।

সাধারণ নীতি: DFA-কে একটি directed graph ভাবলে দৈর্ঘ্য n-এর গৃহীত string-এর সংখ্যা মানে শুরু থেকে accepting state-এ দৈর্ঘ্য n-এর walk-এর সংখ্যা, যা transition matrix-এর n-তম ঘাত থেকে আসে (পর্ব ১৯)। তাই প্রতিটি regular language-এর গণনা একটি linear recurrence মেনে চলে।

প্রমাণের ভুল ধরুন: “(01)* regular নয়”

একজন লিখলেন: “ধরি (01)* regular, pumping length p. s = (01)^p নিই। y = 0 নিই, x = ε. তাহলে i = 2-এ xy²z = 0 0 1 (01)^p−1 = 001…, যা (01)*-এ নেই। বিরোধ, তাই regular নয়। ∎”

ভুল কোথায়: বিভাজন বাছার অধিকার প্রমাণকারীর নয়; lemma শুধু বলে কোনো একটি বিভাজন pump করা যায়। প্রমাণকারীকে দেখাতে হয় প্রতিটি বৈধ বিভাজন ব্যর্থ। এখানে x = ε, y = 01 নিলে (p ≥ 2-এ |xy| = 2 ≤ p) xyⁱz = (01)^p−1+i, সব i-তে ভাষায়। সত্যিই (01)* regular: তার regex তো দেওয়াই আছে, আর ৩ state-এর DFA-ও সহজ। এই ভুল আসে পর্ব ৫-এর ∃ আর ∀-এর ক্রম গুলিয়ে ফেলা থেকে।

১০ · AI-এর যুগে — automaton-এর দাবি যাচাই

AI সহকারী DFA আঁকে আর pumping-এর প্রমাণ লেখে আত্মবিশ্বাসের সঙ্গে, কিন্তু প্রায়ই সূক্ষ্ম ভুল থাকে। কয়েকটি পরিচিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• δ-এর টেবিলে প্রতিটি (state, চিহ্ন) ঘর পূরণ, আর ফাঁকা string-এর সিদ্ধান্ত ঠিক
• ছোট দৈর্ঘ্যের সব string-এ যন্ত্র নিজে চালিয়ে সংজ্ঞার সঙ্গে মিলিয়েছি
• Induction-এর base case আর invariant-এর বক্তব্য স্পষ্ট
• Pumping-এর প্রমাণে বিভাজন প্রতিপক্ষের, আর সব বিভাজন বিবেচিত
• প্রতিটি উপপাদ্যের শর্ত (DFA না NFA, সম্পূর্ণ কি না) মিলিয়েছি
• সাল, নাম আর প্রবন্ধের দাবি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Automaton যাচাই করা সহজ, কারণ যন্ত্র ছোট আর string গোনা যায়: দৈর্ঘ্য 10 পর্যন্ত মাত্র ২০৪৭টি binary string. কিন্তু মনে রাখুন, সসীম গণনা উদাহরণ দেয়, প্রমাণ নয়; প্রমাণ আসে invariant আর induction থেকে।