Finite Automata — DFA, NFA, ও তাদের সমতুল্যতা

Subset construction — NFA থেকে DFA বানানোর যান্ত্রিক পদ্ধতি

এখানেই এই লেসনের কেন্দ্রীয় algorithm। মূল ধারণা: DFA-র প্রতিটা state হবে NFA-র state-এর একটা সেট। DFA প্রতি মুহূর্তে “NFA সম্ভবত কোন কোন state-এ থাকতে পারত” — সেই পুরো সম্ভাবনার সেটটাই একটামাত্র (deterministic!) state হিসেবে ট্র্যাক করে।

Algorithm:

১. DFA-র start state = ECLOSE(NFA-র start state)
২. একটা কাজ-তালিকায় (worklist) এই নতুন state রাখুন
৩. যতক্ষণ worklist খালি না হয়:
     একটা DFA state S (= NFA state-এর সেট) তুলে নিন
     প্রতিটা input symbol a-এর জন্য:
       T = ECLOSE( ∪_{q ∈ S} δ(q, a) )
       DFA-তে transition S --a--> T যোগ করুন
       T যদি নতুন হয়, worklist-এ যোগ করুন
৪. যে DFA state-এ NFA-র কোনো accepting state আছে, সেটাই DFA-র accepting state

সম্পূর্ণ worked example

NFA নিই — Σ = {0,1}, ভাষা: “01” substring থাকতেই হবে, এবার ε-transition-সহ (compilers/lexical-analysis-এর regex→NFA প্যাটার্নের কাছাকাছি একটা রূপ):

states: {A, B, C, D}    (D = accept)
δ(A, 0) = {A, B}
δ(A, 1) = {A}
δ(B, 1) = {C}
δ(C, ε) = {D}
δ(D, 0) = {D}
δ(D, 1) = {D}
start: A,   F = {D}

ECLOSE হিসাব: ECLOSE(A)={A}, ECLOSE(B)={B}, ECLOSE(C)={C,D}, ECLOSE(D)={D} (C-তে ε দিয়ে D-তে যাওয়া যায়, তাই C-র ε-closure-এ D-ও ঢোকে)।

ধাপ ১ — start state: S0 = ECLOSE(A) = {A}

ধাপ ২ — S0 = {A} থেকে:

0: ∪ δ(q,0) for q∈{A} = δ(A,0) = {A,B}
   ECLOSE({A,B}) = {A} ∪ {B} = {A,B}   →  নতুন state S1 = {A,B}

1: ∪ δ(q,1) for q∈{A} = δ(A,1) = {A}
   ECLOSE({A}) = {A}                    →  পুরনো state S0

ধাপ ৩ — S1 = {A,B} থেকে:

0: δ(A,0) ∪ δ(B,0) = {A,B} ∪ ∅ = {A,B}
   ECLOSE({A,B}) = {A,B}                →  পুরনো state S1

1: δ(A,1) ∪ δ(B,1) = {A} ∪ {C} = {A,C}
   ECLOSE({A,C}) = {A} ∪ {C,D} = {A,C,D} → নতুন state S2 = {A,C,D}

ধাপ ৪ — S2 = {A,C,D} থেকে (D accepting, তাই S2 accepting):

0: δ(A,0) ∪ δ(C,0) ∪ δ(D,0) = {A,B} ∪ ∅ ∪ {D} = {A,B,D}
   ECLOSE({A,B,D}) = {A,B,D}            →  নতুন state S3 = {A,B,D}

1: δ(A,1) ∪ δ(C,1) ∪ δ(D,1) = {A} ∪ ∅ ∪ {D} = {A,D}
   ECLOSE({A,D}) = {A,D}                →  নতুন state S4 = {A,D}

ধাপ ৫, ৬ — S3, S4 (উভয়ই D ধারণ করে, তাই accepting):

S3={A,B,D}:  0 → ECLOSE({A,B}∪{D}) = {A,B,D} = S3
             1 → ECLOSE({A}∪{D})   = {A,D}   = S4

S4={A,D}:    0 → ECLOSE({A,B}∪{D}) = {A,B,D} = S3
             1 → ECLOSE({A}∪{D})   = {A,D}   = S4

সব state processed — worklist খালি। ফলাফল DFA:

যাচাই করুন: "001" — S0 →⁰ S1 →⁰ S1 →¹ S2 (accepting, ঠিক আছে, 001-এ 01 substring আছে)। "10" — S0 →¹ S0 →⁰ S1 (non-accepting, ঠিক — 10-এ 01 নেই)।

State blow-up — কেন এটা exponential হতে পারে

উপরের উদাহরণে NFA-র ৪টা state, DFA-র ৫টা — প্রায় সমান। কিন্তু সাধারণভাবে subset construction-এ DFA-র state সংখ্যা 2^|Q_NFA| পর্যন্ত হতে পারে (Q_NFA-র প্রতিটা উপসেটের জন্য একটা DFA state সম্ভব)। এটা ব্যবহারিক নয় শুধু তাত্ত্বিক ভীতি না — একটা ক্লাসিক উদাহরণ:

ভাষা: {w : w-এর ডান দিক থেকে n-তম character 1}

এই ভাষার জন্য একটা (n+1)-state NFA আছে (একটা “guess” state যা যেকোনো মুহূর্তে “এইটাই সেই n-তম থেকে শেষ position” ধরে নিয়ে গোনা শুরু করে), কিন্তু যেকোনো সমতুল্য DFA-র অন্তত 2ⁿ টা state লাগবেই (প্রমাণযোগ্য, Myhill-Nerode theorem দিয়ে) — কারণ DFA-কে শেষ n character-এর প্রতিটা সম্ভাব্য combination আলাদা state-এ মনে রাখতে হয়।

DFA minimization — এক নজরে

Subset construction-এর পরে DFA-তে প্রয়োজনের চেয়ে বেশি state থাকতে পারে — দুইটা state functionally সমান হতে পারে (একই ভবিষ্যৎ আচরণ) অথচ আলাদা লেবেলে আছে। Myhill-Nerode theorem বলে: দুইটা state p, q “equivalent” যদি কোনো suffix w-এর জন্য δ̂(p,w) ∈ F ⟺ δ̂(q,w) ∈ F — অর্থাৎ কোনো ভবিষ্যৎ ইনপুট তাদের আলাদা করতে না পারে।

Partition refinement algorithm (সংক্ষেপে): শুরুতে দুইটা দল — accepting আর non-accepting। বারবার একটা দলকে ভাঙুন যদি তার দুইটা state কোনো symbol-এ ভিন্ন দলে যায়। কোনো দল আর ভাঙা না গেলে থামুন — প্রতিটা অবশিষ্ট দল একটা মিনিমাইজড state।

এটা একটা unique (সেরা সম্ভব) DFA দেয় — Myhill-Nerode theorem এটাও প্রমাণ করে যে এই মিনিমাম DFA আইসোমরফিজম পর্যন্ত অনন্য। আমরা পূর্ণ প্রমাণে যাচ্ছি না, কিন্তু ব্যবহারিক তাৎপর্য বিশাল — lexer generator (flex, re2c) DFA generate করার পরপরই এটা minimize করে, যাতে embedded-এর মতো memory-সংবেদনশীল জায়গায় টেবিল ছোট থাকে।