সরাসরি পর্বে যান
পর্ব ১১ · ৮৫-এর মধ্যে · মডিউল ২

ε-NFA — ε-closure আর ε-transition দূর করা

Epsilon-NFA — Epsilon-Closure, Conversion to DFA and Removing Epsilon-Transitions

Taught in Bangla, this lesson adds ε-transitions, defines ECLOSE(q) and computes it by breadth-first search. It traces input through an ε-NFA with closure after every symbol, converts an ε-NFA to a DFA with a closure-aware subset construction, and removes ε-transitions with δ′(q, a) = ECLOSE(δ(ECLOSE(q), a)) without adding states. In-page Python (Pyodide) runs closure, conversion and removal, a real automata-lib run cross-checks the result, and three common mistakes are caught with counterexamples.

এই পর্বে যা শিখবেন

  • ε-transition কী, কেন দরকার, আর দুটি যন্ত্রকে union ও concatenation-এ জোড়া লাগানো
  • ε-NFA-র 5-tuple সংজ্ঞা, δ: Q × Σε → P(Q), আর পথ দিয়ে গ্রহণের নিয়ম
  • ε-closure-এর সংজ্ঞা, তার তিনটি ধর্ম আর BFS দিয়ে হিসাব
  • ε-NFA থেকে DFA আর ε-NFA থেকে ε-ছাড়া NFA, দুটি রূপান্তর আর তাদের সঠিকতার প্রমাণ
  • Closure-এর তিনটি চেনা ভুল, আর brute force দিয়ে প্রতিটির সবচেয়ে ছোট counterexample খোঁজা

১ · বিনা টিকিটের করিডোর — ε-transition কেন

মেট্রো রেলের একটি বড় স্টেশন কল্পনা করুন। এক প্ল্যাটফর্ম থেকে আরেক প্ল্যাটফর্মে যাওয়ার একটি ভেতরের করিডোর আছে, যেখানে কার্ড ছোঁয়াতে হয় না। আপনি ইচ্ছা করলে করিডোর দিয়ে চলে যেতে পারেন, না-ও যেতে পারেন; কোনো রেকর্ড থাকে না। কার্ড ছোঁয়ানো মানে একটি চিহ্ন পড়া, আর করিডোর মানে ε-transition: এমন একটি তীর, যা ধরে যন্ত্র কোনো চিহ্ন না পড়েই এক state থেকে আরেক state-এ যায়। এখানে ε সেই empty string, যার দৈর্ঘ্য 0 (কিছু বই λ লেখে)।

পর্ব ০৯-এ NFA দেখেছেন: একটি চিহ্নে শূন্য, এক বা একাধিক পরের state. ε-NFA সেখানে আরেকটি স্বাধীনতা যোগ করে: চিহ্ন ছাড়া নড়াচড়া। প্রশ্ন হলো, এতে লাভ কী? উত্তর একটি শব্দে: জোড়া লাগানো।

বাজারঘর আমাদের কাল্পনিক অনলাইন দোকান। তার গুদামের একটি স্ক্যানার প্রতিটি ব্যাচ-কোডকে (0 আর 1-এর string) দুটি পরীক্ষা করে। পরীক্ষা ক: 1-এর সংখ্যা জোড় (পর্ব ০৭-এর parity DFA). পরীক্ষা খ: binary মান 3 দিয়ে বিভাজ্য (পর্ব ০৮-এর mod-3 DFA). নতুন নিয়ম: যেকোনো একটি পরীক্ষায় পাস করলেই কোড বৈধ। দুটি DFA আমাদের হাতে আছে। Product construction দিয়ে 2 × 3 = 6 state-এর একটি DFA বানানো যায়, কিন্তু প্রতিটি জোড়া state নতুন করে হিসাব করতে হয়। ε দিয়ে কাজটি এক লাইনের: একটি নতুন শুরুর state s বানান, আর s থেকে দুটি পুরোনো শুরুর state-এ দুটি ε-তীর দিন। যন্ত্র শুরুতেই “অনুমান” করে কোন পরীক্ষাটি চালাবে, আর কোনো চিহ্ন খরচ না করে সেখানে চলে যায়।

ছবি ১১.১ · ε দিয়ে দুটি যন্ত্র জোড়া

ওপরে union: নতুন শুরুর state s থেকে দুই যন্ত্রের শুরুতে ε. নিচে concatenation: M1-এর প্রতিটি accept state থেকে M2-এর শুরুতে ε, আর M1-এর accept state আর accept থাকে না।

Gluing two automata with epsilon-transitions: union and concatenation union: L(M1) ∪ L(M2) s M1 (parity) M2 (mod 3) ε ε concatenation: L(M1)L(M2) M1 M2 f1 ε বেগুনি ড্যাশ = ε-তীর, কোনো চিহ্ন পড়া হয় না

Concatenation-এ সুবিধা আরও স্পষ্ট। “আগে M1-এর একটি string, তারপর M2-এর একটি string” চিনতে যন্ত্রকে অনুমান করতে হয় প্রথম অংশ কোথায় শেষ। ε-তীর ঠিক সেই অনুমানের জায়গা: M1-এর accept state-এ পৌঁছালে যন্ত্র চাইলে বিনা চিহ্নে M2-এর শুরুতে চলে যায়। Kleene star-এর জন্যও একই কৌশল: accept state থেকে শুরুতে ফেরার ε-তীর। পর্ব ০৯-এ এই জোড়াগুলো ε ছাড়া করেছিলেন, তাতে প্রথম চিহ্নের সারি নকল করতে হয়েছিল। ε থাকলে নির্মাণগুলো প্রায় ছবি আঁকার মতো, আর পর্ব ১৪-এর Thompson construction পুরোটাই এই আঠার ওপর দাঁড়ানো।

ε-তীরকে মোবাইল ব্যাংকিংয়ের মেনুর একটি “স্বয়ংক্রিয় পরের ধাপ” হিসেবেও ভাবতে পারেন: কোনো বোতাম না চাপলেও মেনু নিজে থেকে পরের পর্দায় চলে যেতে পারে। পার্থক্য একটাই: ε-NFA-তে যাওয়াটা বাধ্যতামূলক নয়, একটি সুযোগ। যন্ত্র যেতেও পারে, না-ও যেতে পারে, আর কোনো একটি পছন্দের ক্রম সফল হলেই string গৃহীত।

২ · ε-NFA-র formal definition

এই পর্বের প্রধান উদাহরণ বাজারঘরের প্যাকিং-লাইন। প্রতিটি অর্ডারের ব্যাগে আগে সব চাল (a), তারপর সব ডাল (b), তারপর সব তেল (c) ঢোকে, প্রতিটি যেকোনো পরিমাণে, শূন্যও হতে পারে। স্ক্যানারের log একটি string, Σ = {a, b, c}. বৈধ log-এর language

Labc = { aibjck : i, j, k ≥ 0 }, অর্থাৎ a∗b∗c∗

যেমন ε, abbc, aac, c বৈধ; acb, ba বৈধ নয়। ε-NFA দিয়ে এর নকশা প্রায় বাক্যটির অনুবাদ: q0-তে a-র loop, তারপর একটি ε-তীর q1-এ, q1-এ b-র loop, আরেকটি ε-তীর q2-এ, q2-তে c-র loop. ε-তীরের মানে “এবার পরের পণ্যে চলে যাই”, আর এই সিদ্ধান্তে কোনো চিহ্ন খরচ হয় না।

ছবি ১১.২ · a∗b∗c∗-এর ε-NFA Eabc

তিনটি state, তিনটি loop আর দুটি ε-তীর। শুধু q2 accept, তবু ε গৃহীত, কারণ q0 থেকে দুটি ε-তীরে q2-এ পৌঁছানো যায়।

Epsilon-NFA E_abc for a*b*c* q0 q1 q2 a b c ε ε চাল ডাল তেল
সংজ্ঞা ১১.১ (ε-NFA)

একটি ε-NFA হলো একটি 5-tuple E = (Q, Σ, δ, q0, F), যেখানে Q সসীম state-এর সেট, Σ একটি alphabet, q0 ∈ Q শুরুর state, F ⊆ Q accept state-এর সেট, আর

δ: Q × Σε → P(Q), যেখানে Σε = Σ ∪ {ε}

অর্থাৎ δ(q, a) হলো a পড়ে q থেকে যাওয়ার state-গুলো, আর δ(q, ε) হলো q থেকে চিহ্ন না পড়ে যাওয়ার state-গুলো। দুটিই Q-এর উপসেট, power set P(Q)-এর উপাদান, আর ∅-ও হতে পারে। ধরে নেওয়া হয় ε ∉ Σ: ε কোনো চিহ্ন নয়, “চিহ্নের অনুপস্থিতি”।

এই কোর্সের Sipser-ধাঁচের রীতিতে পর্ব ০৯-এর NFA আসলে এই সংজ্ঞারই বিশেষ রূপ, যেখানে প্রতিটি δ(q, ε) = ∅. Eabc-এর transition table-এ তাই একটি বাড়তি ε কলাম। তীর (→) শুরুর state, তারা (∗) accept state.

stateabcε
→ q0{q0}∅∅{q1}
q1∅{q1}∅{q2}
∗ q2∅∅{q2}∅

পথ দিয়ে গ্রহণ

ε-NFA-তে একটি পথ চিহ্ন পড়ার ধাপ আর ε-ধাপ মিশিয়ে চলে। তাই পথের দৈর্ঘ্য string-এর দৈর্ঘ্যের চেয়ে বেশি হতে পারে।

সংজ্ঞা ১১.২ (ε-NFA-র গ্রহণ, পথের রূপে)

E একটি string w গ্রহণ করে, যদি w-কে w = y1y2⋯ym আকারে লেখা যায়, যেখানে প্রতিটি yi ∈ Σε, আর state-এর এমন ক্রম r0, r1, …, rm থাকে যে

  1. r0 = q0;
  2. প্রতিটি i = 0, …, m − 1-এর জন্য ri+1 ∈ δ(ri, yi+1);
  3. rm ∈ F.

yi-গুলোর মধ্যে যেগুলো ε, সেগুলো জোড়া দিলে কিছুই যোগ হয় না, তাই m ≥ |w|. L(E) হলো E-এর গৃহীত সব string-এর সেট।

উদাহরণ: w = ac. লেখা যায় ac = a · ε · ε · c, আর পথ q0 →a q0 →ε q1 →ε q2 →c q2. শেষ state q2 ∈ F, তাই ac গৃহীত। m = 4, অথচ |w| = 2. আবার w = ε-এর জন্য ε = ε · ε, পথ q0 →ε q1 →ε q2, তাই ε ∈ L(Eabc). লক্ষ করুন, q0 accept state নয়, তবু ε গৃহীত। ε-NFA-তে “ε গৃহীত কি না” শুধু q0 ∈ F দেখে বলা যায় না; এই সূক্ষ্মতাই পরে সবচেয়ে বেশি ভুলের উৎস হবে।

৩ · ε-closure — সংজ্ঞা, ধর্ম আর BFS

পথের সংজ্ঞা নির্ভুল, কিন্তু হিসাবের জন্য অসুবিধাজনক: কোথায় কয়টি ε বসবে, তার অসংখ্য বিকল্প। সমাধান হলো সব ε-লাফ একবারে গুছিয়ে নেওয়া। একটি state থেকে শুধু ε-তীর ধরে যেখানে যেখানে যাওয়া যায়, সেই সেটের নাম ε-closure.

সংজ্ঞা ১১.৩ (ε-closure)

State q-এর ε-closure ECLOSE(q) হলো Q-এর ক্ষুদ্রতম উপসেট R, যার জন্য

  1. q ∈ R, আর
  2. p ∈ R এবং r ∈ δ(p, ε) হলে r ∈ R.

সমতুল্যভাবে, ECLOSE(q) = { r : q থেকে শূন্য বা বেশি ε-তীর ধরে r-এ যাওয়া যায় }. একটি সেট S-এর জন্য ECLOSE(S) = ⋃q ∈ S ECLOSE(q), আর ECLOSE(∅) = ∅. Sipser একে E(S) লেখেন, Hopcroft–Motwani–Ullman লেখেন ECLOSE.

“শূন্য বা বেশি ধাপ” কথাটিই মূল: শূন্য ধাপে q নিজের কাছেই থাকে, তাই q ∈ ECLOSE(q) সবসময়। গণিতের ভাষায়, “p থেকে একটি ε-তীরে r” একটি relation, আর ECLOSE তার reflexive-transitive closure (পর্ব ০২-এর প্রয়োজনীয় গণিত; গভীরে ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৪)। ছবির ভাষায়, শুধু ε-তীরগুলো রেখে একটি directed graph বানালে ECLOSE(q) হলো q থেকে পৌঁছানো যায় এমন সব vertex. তাই হিসাবের algorithm হলো সাধারণ BFS.

Algorithm ১১.১ (BFS দিয়ে ECLOSE(S))
  1. seen ← S; queue ← S-এর সব state.
  2. queue ফাঁকা না হওয়া পর্যন্ত: queue-র সামনে থেকে p তুলুন; প্রতিটি r ∈ δ(p, ε)-এর জন্য r ∉ seen হলে r-কে seen আর queue-তে যোগ করুন।
  3. seen-ই ECLOSE(S).

প্রতিটি state queue-তে বড়জোর একবার ঢোকে, আর প্রতিটি ε-তীর বড়জোর একবার দেখা হয়। তাই সময় O(|Q| + e), যেখানে e হলো ε-তীরের সংখ্যা। seen না রাখলে ε-তীরের চক্রে algorithm চিরকাল ঘুরত। Queue-র বদলে stack নিলে DFS হয়, ফল একই সেট।

নিচের stepper শুধু ε-তীর আছে এমন একটি ছোট graph-এ ECLOSE(q0) হিসাব করে। এতে ইচ্ছা করে একটি চক্র (q1 → q3 → q1) আর একটি উল্টো দিকের তীর (q5 → q0) রাখা হয়েছে।

BFS computing the epsilon-closure of q0 on an epsilon-only graph ε ε ε ε ε ε ε q5 q0 q1 q2 q3 q4
BFS-এর অবস্থা
তোলা state
নতুন পাওয়া
queue
seen
  1. শুরু। শূন্য ধাপের পথে q0 নিজের কাছেই থাকে, তাই seen = {q0}, queue = [q0]. এই প্রথম ধাপটি ভুলে গেলে closure থেকে q নিজেই হারিয়ে যায়।
  2. q0 তোলা। δ(q0, ε) = {q1, q2}. দুটিই নতুন, তাই seen = {q0, q1, q2}, queue = [q1, q2].
  3. q1 তোলা। δ(q1, ε) = {q3}, নতুন। seen-এ q3 যোগ হলো, queue = [q2, q3].
  4. q2 তোলা। δ(q2, ε) = {q3}, কিন্তু q3 আগেই seen-এ। কিছু যোগ হলো না, queue = [q3]. দুটি আলাদা পথে একই state-এ পৌঁছানো স্বাভাবিক; seen তাকে দুবার গোনা থেকে বাঁচায়।
  5. q3 তোলা। δ(q3, ε) = {q1, q4}. q1 আগেই seen, তাই চক্রটি এখানেই থামে; q4 নতুন। seen = {q0, q1, q2, q3, q4}, queue = [q4].
  6. q4 তোলা। q4 থেকে কোনো ε-তীর নেই। queue এখন ফাঁকা।
  7. ফল। ECLOSE(q0) = {q0, q1, q2, q3, q4}. q5 নেই, যদিও q5 আর q0 একটি তীরে যুক্ত: তীরটির দিক q5 থেকে q0, উল্টো নয়। Closure সবসময় তীরের দিক মেনে চলে।
লেমা ১১.১ (ECLOSE-এর তিনটি ধর্ম)

Q-এর যেকোনো উপসেট S আর T-এর জন্য

  1. S ⊆ ECLOSE(S) (প্রসারী);
  2. ECLOSE(ECLOSE(S)) = ECLOSE(S) (দুবার নিলে কিছু বদলায় না);
  3. ECLOSE(S ∪ T) = ECLOSE(S) ∪ ECLOSE(T).

প্রমাণ। (১) শূন্য ধাপের পথ থেকে সরাসরি। (২) ⊇ দিক (১) থেকে আসে। ⊆ দিকের জন্য ধরুন r ∈ ECLOSE(ECLOSE(S)). তাহলে কোনো p ∈ ECLOSE(S) থেকে r-এ একটি ε-পথ আছে, আর কোনো q ∈ S থেকে p-তে একটি ε-পথ আছে। দুটি পথ জুড়ে q থেকে r-এ একটি ε-পথ পাওয়া যায়, তাই r ∈ ECLOSE(S). (৩) সংজ্ঞায় ECLOSE(S) হলো প্রতিটি সদস্যের closure-এর union, তাই S ∪ T-এর সদস্যদের closure-এর union দুই ভাগে ভাগ করা যায়। ∎

ধর্ম (২)-এর একটি নাম আছে: যে সেট S-এর জন্য ECLOSE(S) = S, তাকে বলি ε-বদ্ধ (closed) সেট। পরের অনুচ্ছেদগুলোর সব হিসাবের মূল নীতি: যেকোনো মুহূর্তের state-এর সেট সবসময় ε-বদ্ধ রাখুন।

নিচের Pyodide ব্লক (আপনার ব্রাউজারে চলা আসল CPython) stepper-এর graph-এ algorithm ১১.১ চালায় আর প্রতিটি তোলার পর queue ছাপে, তারপর সব state-এর closure আর ধর্ম (২) পরীক্ষা করে। প্রথমবার চালালে Python নামতে কয়েক সেকেন্ড লাগে।

from collections import deque
# only the epsilon-edges matter for the closure
eps = {"q0": ["q1", "q2"], "q1": ["q3"], "q2": ["q3"],
       "q3": ["q1", "q4"], "q5": ["q0"]}

def show(S):
    return "{" + ",".join(sorted(S)) + "}"

def eclose(start, trace=False):
    seen, queue = set(start), deque(sorted(start))
    while queue:
        p = queue.popleft()
        new = [r for r in eps.get(p, []) if r not in seen]
        seen.update(new)
        queue.extend(new)
        if trace:
            print(f"  pop {p}: new {new}  queue {list(queue)}")
    return seen

print("BFS from q0")
print("ECLOSE(q0) =", show(eclose({"q0"}, trace=True)))
for q in ["q1", "q2", "q3", "q4", "q5"]:
    print(f"ECLOSE({q}) =", show(eclose({q})))
print("ECLOSE({q2,q4}) =", show(eclose({"q2", "q4"})))
once = eclose({"q0"})
print("closing twice changes nothing:", eclose(once) == once)

আসল আউটপুট (ব্রাউজারের Python):

BFS from q0
  pop q0: new ['q1', 'q2']  queue ['q1', 'q2']
  pop q1: new ['q3']  queue ['q2', 'q3']
  pop q2: new []  queue ['q3']
  pop q3: new ['q4']  queue ['q4']
  pop q4: new []  queue []
ECLOSE(q0) = {q0,q1,q2,q3,q4}
ECLOSE(q1) = {q1,q3,q4}
ECLOSE(q2) = {q1,q2,q3,q4}
ECLOSE(q3) = {q1,q3,q4}
ECLOSE(q4) = {q4}
ECLOSE(q5) = {q0,q1,q2,q3,q4,q5}
ECLOSE({q2,q4}) = {q1,q2,q3,q4}
closing twice changes nothing: True

প্রথম পাঁচ লাইন হুবহু stepper-এর পাঁচটি তোলা। খেয়াল করুন, ECLOSE(q1) = ECLOSE(q3) = {q1, q3, q4}: একই ε-চক্রে থাকা দুটি state-এর closure সমান, কারণ তারা একে অপরের কাছে বিনা খরচে যেতে পারে। ECLOSE(q5) সবচেয়ে বড়, কারণ q5 থেকে q0 হয়ে সবখানে যাওয়া যায়। ECLOSE({q2, q4}) হলো ECLOSE(q2) ∪ ECLOSE(q4), লেমা ১১.১-এর ধর্ম (৩), আর শেষ লাইন ধর্ম (২) যাচাই করে। এটি একটি উদাহরণে যাচাই, প্রমাণ নয়; প্রমাণ ওপরে।

৪ · ε-NFA-র δ̂ আর একটি input-এর trace

Closure হাতে থাকলে পুরো string-এর হিসাব আবার একটি সরল induction. পর্ব ০৯-এর NFA-তে শুরু ছিল {q}, আর প্রতিটি চিহ্নে “move” নেওয়া হতো। ε-NFA-তে দুটি জায়গায় closure যোগ হয়: শুরুতে, আর প্রতিটি move-এর পরে।

সংজ্ঞা ১১.৪ (ε-NFA-র δ̂ আর language)

একটি সেট S আর চিহ্ন a-র জন্য move(S, a) = ⋃p ∈ S δ(p, a). তারপর প্রতিটি q ∈ Q, w ∈ Σ∗, a ∈ Σ-এর জন্য

δ̂(q, ε) = ECLOSE(q), δ̂(q, wa) = ECLOSE( move( δ̂(q, w), a ) )
L(E) = { w ∈ Σ∗ : δ̂(q0, w) ∩ F ≠ ∅ }

এটি extended transition function-এর ε-NFA রূপ (কিছু বইয়ে δ∗)। সংজ্ঞা থেকেই প্রতিটি δ̂(q, w) একটি ε-বদ্ধ সেট।

লেমা ১১.২ (দুই সংজ্ঞা একই কথা বলে)

প্রতিটি w-এর জন্য δ̂(q0, w) = { r : সংজ্ঞা ১১.২-এর অর্থে q0 থেকে r-এ এমন একটি পথ আছে, যার চিহ্নগুলো থেকে ε বাদ দিলে w থাকে }. তাই δ̂ দিয়ে L(E) আর পথ দিয়ে L(E) একই সেট।

প্রমাণের রূপরেখা। |w|-এর ওপর induction. |w| = 0: যে পথের সব চিহ্ন ε, তা শুধু ε-তীরের পথ, আর তার শেষ বিন্দুগুলো ঠিক ECLOSE(q0). ধাপ: w = va-র প্রতিটি পথকে শেষ a-তীরের জায়গায় তিন টুকরো করুন: v-এর একটি পথ (শেষ বিন্দু কোনো p, induction-এ p ∈ δ̂(q0, v)), তারপর একটি a-তীর p থেকে কোনো s ∈ δ(p, a)-তে, তারপর শুধু ε-তীরের একটি পথ s থেকে r-এ (তাই r ∈ ECLOSE(s)). এমন r-এর সেট ঠিক ECLOSE(move(δ̂(q0, v), a)) = δ̂(q0, va). উল্টো দিকে এই তিন টুকরো জুড়লেই একটি পথ। একটি সূক্ষ্মতা: v-এর পথের শেষে যে ε-তীরগুলো থাকে, সেগুলো v-এর অংশ হিসেবেই গোনা হয়; induction-এর অনুমানে δ̂(q0, v) ε-বদ্ধ বলে তারা ঠিকই ধরা পড়ে। ∎

নিচের stepper Eabc-কে input acb-তে চালায়। প্রতিটি চিহ্নকে দুই ধাপে ভাঙা হয়েছে, move আর close, যাতে কোথায় closure লাগে তা চোখে পড়ে। সবুজ বৃত্ত মানে সেই ধাপের সেটে থাকা state.

Trace of E_abc on input acb, move then close q0 q1 q2 a b c ε ε সেট ∅ — সব পথ মৃত
Simulation-এর অবস্থা
পড়া অংশ
কাজ
S
S ∩ F
  1. শুরু = closure. কিছু পড়ার আগেই S = ECLOSE(q0) = {q0, q1, q2}. এতে q2 ∈ F আছে, তাই এখানে থামলে ε গৃহীত হতো। শুরুর সেটকে {q0} ধরা ε-NFA-র সবচেয়ে চেনা ভুল।
  2. a: move. S-এর তিন state-এর মধ্যে শুধু q0-র a-তীর আছে: move = {q0}. এটি এখনো ε-বদ্ধ নয়।
  3. a: close. ECLOSE({q0}) = {q0, q1, q2}. এই ধাপ বাদ দিলে পরের b বা c আর পড়া যেত না, আর “ab”-এর মতো বৈধ log বাতিল হতো।
  4. c: move. q0 আর q1-এর c-তীর নেই; q2-এর আছে। move = {q2}. ডাল-ধাপটি শূন্যবার ঘটল, কোনো সমস্যা নেই।
  5. c: close. q2 থেকে কোনো ε-তীর নেই, তাই ECLOSE({q2}) = {q2}. যন্ত্র এখন “তেলের পর্বে”, পেছনে ফেরার কোনো তীর নেই।
  6. b: move. q2-এর b-তীর নেই: move = ∅. সব পথ মরে গেল; ECLOSE(∅) = ∅, তাই বাকি input যা-ই হোক, সেট ∅-ই থাকবে।
  7. সিদ্ধান্ত। শেষ সেট ∅, S ∩ F = ∅, তাই acb বাতিল। ঠিকই আছে: তেলের পরে ডাল এসেছে, ক্রম ভেঙেছে।

এবার নিজে চালান। নিচের JavaScript ব্লক একই হিসাব করে, তবে closure-এর জন্য queue-র বদলে stack (DFS) ব্যবহার করে; ধর্ম অনুযায়ী ফল একই হওয়ার কথা। INPUTS বদলে আবার চালিয়ে দেখুন।

// epsilon-NFA for a*b*c*. Edit INPUTS and press Run again.
const delta = { "q0,a": ["q0"], "q1,b": ["q1"], "q2,c": ["q2"] };
const eps = { q0: ["q1"], q1: ["q2"] };
const F = new Set(["q2"]);
const INPUTS = ["abbc", "acb", ""];

function eclose(S) {                     // DFS with a stack; BFS gives the same set
  const seen = new Set(S), stack = [...S];
  while (stack.length) {
    const p = stack.pop();
    for (const r of eps[p] || []) if (!seen.has(r)) { seen.add(r); stack.push(r); }
  }
  return seen;
}
const show = S => S.size ? "{" + [...S].sort().join(",") + "}" : "∅";

for (const w of INPUTS) {
  let cur = eclose(["q0"]);               // the start set is a closure
  console.log(`input "${w}"  start ${show(cur)}`);
  for (const a of w) {
    const moved = new Set();
    for (const p of cur) for (const r of delta[p + "," + a] || []) moved.add(r);
    cur = eclose(moved);                  // close after EVERY symbol
    console.log(`  ${a}: move ${show(moved)}  close ${show(cur)}`);
  }
  console.log("  verdict:", [...cur].some(q => F.has(q)) ? "ACCEPT" : "reject");
}

আসল আউটপুট (ব্রাউজারের JavaScript):

input "abbc"  start {q0,q1,q2}
  a: move {q0}  close {q0,q1,q2}
  b: move {q1}  close {q1,q2}
  b: move {q1}  close {q1,q2}
  c: move {q2}  close {q2}
  verdict: ACCEPT
input "acb"  start {q0,q1,q2}
  a: move {q0}  close {q0,q1,q2}
  c: move {q2}  close {q2}
  b: move ∅  close ∅
  verdict: reject
input ""  start {q0,q1,q2}
  verdict: ACCEPT

দ্বিতীয় অংশ হুবহু stepper-এর সাত ধাপ। abbc-তে দেখুন, b পড়ার পর move শুধু {q1}, আর closure সেখানে q2 যোগ করে, যাতে পরের c পড়া যায়। শেষ input খালি string: কোনো চিহ্ন নেই, তাই শুধু শুরুর closure-ই সিদ্ধান্ত দেয়, আর তাতে q2 আছে বলে ε গৃহীত। এখানে q0 ∉ F হলেও উত্তর ACCEPT, যা অনুচ্ছেদ ২-এর সূক্ষ্মতা।

৫ · ε-NFA থেকে DFA — closure-সহ subset construction

পর্ব ১০-এ (NFA থেকে DFA) দেখেছেন, সম্ভাব্য state-এর প্রতিটি সেটকে একটি DFA state বানালেই NFA-র সমতুল্য DFA পাওয়া যায়। ε-NFA-র জন্য সেই subset construction-এ বদলায় ঠিক দুটি জায়গা, যা stepper-এ দেখলেন: শুরুর সেট আর প্রতিটি চিহ্নের পরের closure.

সংজ্ঞা ১১.৫ (closure-সহ subset construction)

ε-NFA E = (Q, Σ, δ, q0, F) থেকে DFA D = (QD, Σ, δD, A, FD):

  1. শুরুর state A = ECLOSE(q0);
  2. প্রতিটি S ∈ QD আর a ∈ Σ-এর জন্য δD(S, a) = ECLOSE(move(S, a));
  3. QD = A থেকে δD ধরে পৌঁছানো যায় এমন সব সেট (শুধু reachable সেট; ∅ এলে সেটি dead state);
  4. FD = { S ∈ QD : S ∩ F ≠ ∅ }.

D-এর alphabet Σ, Σε নয়: DFA-তে কোনো ε কলাম থাকে না। প্রতিটি QD-এর সদস্য ε-বদ্ধ, তাই সবচেয়ে খারাপ ক্ষেত্রে 2|Q|টি সেট, পর্ব ১০-এর মতো।

নিচের stepper Eabc-কে এই নিয়মে সারি ধরে DFA বানায়। নামগুলো A, B, C, D ক্রমে আবিষ্কারের ক্রম।

নির্মাণের অবস্থা
এই হিসাব
move
ECLOSE
জানা সেট
  1. শুরুর state. A = ECLOSE(q0) = {q0, q1, q2}. A-তে q2 আছে, তাই A ∈ FD: DFA ε গ্রহণ করে, যেমন করা উচিত।
  2. A, a. move(A, a) = δ(q0, a) = {q0}; ECLOSE({q0}) = {q0, q1, q2} = A. পুরোনো সেট, নতুন state নয়: চালের পর আরও চাল এলে যন্ত্র একই জায়গায়।
  3. A, b. move(A, b) = δ(q1, b) = {q1}; ECLOSE({q1}) = {q1, q2}. নতুন সেট, নাম B; এতে q2 আছে বলে B accept.
  4. A, c. move(A, c) = {q2}; ECLOSE = {q2}, নতুন, নাম C, accept.
  5. B, a. B = {q1, q2}-এর কারও a-তীর নেই: move = ∅, ECLOSE(∅) = ∅. নতুন সেট D = ∅, যা dead state: ডালের পরে চাল এলে আর ফেরা নেই।
  6. B, b আর B, c. move(B, b) = {q1}, closure B; move(B, c) = {q2}, closure C. দুটিই পুরোনো।
  7. C-র সারি। C = {q2}: a আর b-তে ∅ = D, c-তে {q2} = C.
  8. D-র সারি আর শেষ। ∅ থেকে সব চিহ্নে ∅. কোনো নতুন সেট নেই, নির্মাণ শেষ। DFA-তে ৪টি state; FD = {A, B, C}, কারণ তিনটিতেই q2 আছে। 23 = 8টি সম্ভাব্য উপসেটের মধ্যে মাত্র ৪টিতে পৌঁছানো গেছে।
DFA stateε-NFA-র সেটabc
→ ∗ A{q0, q1, q2}ABC
∗ B{q1, q2}DBC
∗ C{q2}DDC
D∅DDD
উপপাদ্য ১১.১ (ε-NFA = DFA)

প্রতিটি ε-NFA E-এর জন্য সংজ্ঞা ১১.৫-এর DFA D-তে L(D) = L(E). ফলে ε-NFA-র চেনা প্রতিটি language regular.

প্রমাণ। দাবি: প্রতিটি w ∈ Σ∗-এর জন্য δ̂D(A, w) = δ̂E(q0, w). |w|-এর ওপর induction.

  1. ভিত্তি, w = ε: δ̂D(A, ε) = A = ECLOSE(q0) = δ̂E(q0, ε). — DFA-র δ̂-এর সংজ্ঞা; সংজ্ঞা ১১.৫-এর ধাপ ১; সংজ্ঞা ১১.৪
  2. অনুমান: v-এর জন্য δ̂D(A, v) = δ̂E(q0, v). — induction hypothesis
  3. w = va হলে δ̂D(A, va) = δD(δ̂D(A, v), a). — DFA-র δ̂-এর সংজ্ঞা
  4. = δD(δ̂E(q0, v), a) = ECLOSE(move(δ̂E(q0, v), a)). — ধাপ ২; সংজ্ঞা ১১.৫-এর ধাপ ২
  5. = δ̂E(q0, va). — সংজ্ঞা ১১.৪
  6. তাই w ∈ L(D) ⇔ δ̂D(A, w) ∈ FD ⇔ δ̂E(q0, w) ∩ F ≠ ∅ ⇔ w ∈ L(E). — FD-এর সংজ্ঞা আর দাবি ∎

প্রমাণটি পর্ব ১০-এর প্রমাণের প্রায় হুবহু কপি; শুধু ভিত্তি-ধাপে {q0}-এর জায়গায় ECLOSE(q0), আর ধাপ ৪-এ বাড়তি ECLOSE. এখান থেকেই বোঝা যায়, শুরুর closure বাদ দিলে ভিত্তি-ধাপ ভেঙে পড়ে, আর পরের closure বাদ দিলে ধাপ ৪ ভেঙে পড়ে।

নিচের ব্লক নির্মাণটি কোডে করে, টেবিল ছাপে, তারপর দৈর্ঘ্য 8 পর্যন্ত সব string-এ DFA-কে একটি স্বাধীন সংজ্ঞার সঙ্গে মেলায়। a∗b∗c∗-এর একটি সুন্দর বৈশিষ্ট্য: w এই language-এ ঠিক তখন, যখন w-এর অক্ষরগুলো ইতিমধ্যে বর্ণানুক্রমে সাজানো, অর্থাৎ w == "".join(sorted(w)).

from collections import deque
from itertools import product
# epsilon-NFA for a*b*c*: q0 -eps-> q1 -eps-> q2
delta = {("q0", "a"): {"q0"}, ("q1", "b"): {"q1"}, ("q2", "c"): {"q2"}}
eps = {"q0": {"q1"}, "q1": {"q2"}}
start, F, sigma = "q0", {"q2"}, "abc"
def eclose(S):
    seen, todo = set(S), list(S)
    while todo:
        new = eps.get(todo.pop(), set()) - seen
        seen |= new; todo += new
    return frozenset(seen)

def step(S, a):                       # move on a, THEN close
    return eclose({r for p in S for r in delta.get((p, a), ())})
show = lambda S: "{" + ",".join(sorted(S)) + "}" if S else "∅"
A = eclose({start})                   # the start state is a closure too
names, todo, table = {A: "A"}, deque([A]), {}
while todo:
    S = todo.popleft()
    for a in sigma:
        T = table[S, a] = step(S, a)
        if T not in names:
            names[T] = "ABCDEFGH"[len(names)]; todo.append(T)
for S, n in names.items():
    row = "  ".join(f"{a}->{names[table[S, a]]}" for a in sigma)
    print(f"{n} = {show(S):10} {row}  {'accept' if S & F else ''}".rstrip())

def dfa_accepts(w):
    S = A
    for a in w: S = table[S, a]
    return bool(S & F)
words = ["".join(t) for n in range(9) for t in product(sigma, repeat=n)]
bad = [w for w in words if dfa_accepts(w) != (w == "".join(sorted(w)))]
print("strings checked:", len(words), " mismatches:", len(bad))

আসল আউটপুট (ব্রাউজারের Python):

A = {q0,q1,q2} a->A  b->B  c->C  accept
B = {q1,q2}    a->D  b->B  c->C  accept
C = {q2}       a->D  b->D  c->C  accept
D = ∅          a->D  b->D  c->D
strings checked: 9841  mismatches: 0

চারটি সারি হুবহু stepper-এর টেবিল। শেষ লাইনে 30 + 31 + ⋯ + 38 = 9841টি string-এ একটিও অমিল নেই। Python-এর frozenset দরকার, কারণ সেটকেই dict-এর key (DFA state-এর নাম) বানাতে হয়। মনে রাখবেন, এটি brute force যাচাই, প্রমাণ নয়; প্রমাণ উপপাদ্য ১১.১-এ।

৬ · ε-transition দূর করা — ε-NFA থেকে সাধারণ NFA

সবসময় পুরো DFA চাই না। কখনো শুধু ε-তীরগুলো সরাতে চাই, কিন্তু state-এর সংখ্যা একই রাখতে চাই, কারণ DFA-তে state 2|Q| পর্যন্ত হতে পারে। এই রূপান্তরকে বলে ε-removal. ধারণাটি সহজ: “ε-লাফ, তারপর একটি চিহ্ন, তারপর আবার ε-লাফ” পুরোটাকে একটি নতুন সরাসরি তীরে বদলে দিন।

সংজ্ঞা ১১.৬ (ε-removal)

ε-NFA E = (Q, Σ, δ, q0, F) থেকে ε-ছাড়া NFA N = (Q, Σ, δ′, q0, F′), একই state, একই শুরু:

δ′(q, a) = ECLOSE( move( ECLOSE(q), a ) )
F′ = { q ∈ Q : ECLOSE(q) ∩ F ≠ ∅ }

প্রথম সূত্রের অর্থ: q থেকে আগে যত খুশি ε, তারপর একটি a, তারপর আবার যত খুশি ε. দ্বিতীয় সূত্রের অর্থ: q থেকে বিনা চিহ্নে কোনো accept state-এ যাওয়া গেলে q নিজেই accept হবে।

Eabc-তে সব state-এর closure-এ q2 আছে, তাই F′ = {q0, q1, q2}, অর্থাৎ নতুন NFA-তে সব state accept. Transition table:

stateECLOSEabc
→ ∗ q0{q0, q1, q2}{q0, q1, q2}{q1, q2}{q2}
∗ q1{q1, q2}∅{q1, q2}{q2}
∗ q2{q2}∅∅{q2}

এক নজরে মিলিয়ে নিন: q0-র সারিতে b-তে {q1, q2}, কারণ q0 থেকে ε-লাফে q1, সেখান থেকে b-তে q1, তারপর ε-লাফে q2. State তিনটিই আছে, কিন্তু তীর ২টি ε আর ৩টি loop থেকে বেড়ে এখন ১০টি সাধারণ তীর। এটিই ε-removal-এর সাধারণ দাম: state বাড়ে না, তীর বাড়তে পারে, সবচেয়ে খারাপ ক্ষেত্রে |Q|2 · |Σ| পর্যন্ত।

উপপাদ্য ১১.২ (ε-removal সঠিক)

সংজ্ঞা ১১.৬-এর N-এর জন্য L(N) = L(E). তাই প্রতিটি ε-NFA-র সমান state-সংখ্যার একটি ε-ছাড়া NFA আছে।

প্রমাণ। প্রথমে একটি সহায়ক দাবি: প্রতিটি অশূন্য w-এর জন্য δ̂N(q0, w) = δ̂E(q0, w). |w|-এর ওপর induction.

  1. ভিত্তি, w = a: δ̂N(q0, a) = δ′(q0, a) = ECLOSE(move(ECLOSE(q0), a)) = δ̂E(q0, a). — N-এ ε নেই; সংজ্ঞা ১১.৬; সংজ্ঞা ১১.৪
  2. ধাপ, w = va, v ≠ ε: S = δ̂N(q0, v) = δ̂E(q0, v), আর S ε-বদ্ধ। — induction hypothesis; সংজ্ঞা ১১.৪-এর পরের মন্তব্য
  3. δ̂N(q0, va) = ⋃p ∈ S δ′(p, a) = ⋃p ∈ S ECLOSE(move(ECLOSE(p), a)) = ECLOSE(move(ECLOSE(S), a)). — NFA-র δ̂; লেমা ১১.১-এর ধর্ম (৩), আর move-ও union-এর ওপর ভাগ হয়
  4. S ε-বদ্ধ, তাই ECLOSE(S) = S, আর ফল ECLOSE(move(S, a)) = δ̂E(q0, va). — ধাপ ২; সংজ্ঞা ১১.৪
  5. w = ε: ε ∈ L(N) ⇔ q0 ∈ F′ ⇔ ECLOSE(q0) ∩ F ≠ ∅ ⇔ ε ∈ L(E). — F′-এর সংজ্ঞা
  6. w ≠ ε: S = δ̂E(q0, w) ε-বদ্ধ। S ∩ F-এ p থাকলে p ∈ F′ (কারণ p ∈ ECLOSE(p)); উল্টোভাবে p ∈ S ∩ F′ হলে ECLOSE(p) ⊆ S-এ একটি accept state আছে। তাই S ∩ F′ ≠ ∅ ⇔ S ∩ F ≠ ∅. — লেমা ১১.১ ∎

ধাপ ৫ দেখায়, F′-এর বদল আসলে শুধু খালি string-এর জন্য জরুরি; ধাপ ৬ দেখায়, অশূন্য string-এ সেট ε-বদ্ধ বলে পুরোনো F-ই কাজ করত। এই কারণে কিছু বই F′ = F ∪ {q0} (যদি ECLOSE(q0) ∩ F ≠ ∅) লেখে, আর কিছু বই δ′-এর শেষ closure বাদ দিয়ে সব q-এর জন্য F′ বদলায়। সংস্করণ আলাদা, language একই; তবে যে সংস্করণ নেবেন, তার সব অংশ একসঙ্গে নিতে হবে। এক বইয়ের δ′ আর আরেক বইয়ের F′ মেশালে ভুল হতে পারে।

সত্যিকারের run: automata-lib দিয়ে মিলিয়ে নেওয়া

Python-এর automata-lib (MIT লাইসেন্স) প্যাকেজে ε লেখা হয় ফাঁকা string "" দিয়ে। এর eliminate_lambda method ε দূর করে (নামটি λ-রীতি থেকে), আর DFA.from_nfa closure-সহ subset construction চালায়। নিচের আউটপুট আমাদের নিজের computer-এ সত্যিকারের run (automata-lib 9.2.0, Python 3.12):

from automata.fa.nfa import NFA
from automata.fa.dfa import DFA

# a*b*c* as an epsilon-NFA; automata-lib writes epsilon as ""
E = NFA(states={"q0", "q1", "q2"}, input_symbols={"a", "b", "c"},
        transitions={"q0": {"a": {"q0"}, "": {"q1"}},
                     "q1": {"b": {"q1"}, "": {"q2"}},
                     "q2": {"c": {"q2"}}},
        initial_state="q0", final_states={"q2"})

for w in ["", "abbc", "acb"]:
    print(repr(w).ljust(7), E.accepts_input(w))

N = E.eliminate_lambda()               # epsilon-NFA -> NFA, no "" keys left
print("NFA final states:", sorted(N.final_states))
for q in sorted(N.transitions):
    row = {a: sorted(t) for a, t in sorted(N.transitions[q].items())}
    print(" ", q, row)

D = DFA.from_nfa(E)                    # subset construction with closure
print("DFA states:", len(D.states), " minimal:", len(D.minify().states))
print("same language as NFA:", D == DFA.from_nfa(N))
$ uv run python enfa_lib.py
''      True
'abbc'  True
'acb'   False
NFA final states: ['q0', 'q1', 'q2']
  q0 {'a': ['q0'], 'b': ['q1', 'q2'], 'c': ['q2']}
  q1 {'b': ['q1'], 'c': ['q2']}
  q2 {'c': ['q2']}
DFA states: 3  minimal: 3
same language as NFA: True

প্রথম তিন লাইন আমাদের trace-এর সঙ্গে মেলে। F′ = {q0, q1, q2}, আমাদের টেবিলের মতোই। কিন্তু একটি ঘর আলাদা: library-র q0-র a-সারিতে শুধু {q0}, আমাদের টেবিলে {q0, q1, q2}. দুটিই ঠিক, কারণ library নিজের state থেকে মূল তীরটি রাখে আর পরের ধাপে closure-এর কাজটি F′ ও পরের সারিগুলো দিয়ে পুষিয়ে নেয়: q0 এমনিতেই accept, আর q0-র সারিতে b ও c-র তীর আছে। ε-removal-এর ফল অনন্য নয়, language অনন্য। শেষ লাইন সেটাই যাচাই করে: দুই রূপ থেকে বানানো DFA সমান (library-র == দুটি DFA-র language তুলনা করে)। DFA-তে ৩টি state, আমাদের ৪টি নয়, কারণ library এখানে partial DFA বানায়: ∅ dead state-টি রাখে না, না-থাকা তীর মানেই বর্জন।

৭ · তিনটি চেনা ভুল আর তাদের counterexample

ε-NFA-র প্রায় সব ভুল একটি প্রশ্নে আটকে যায়: “closure কোথায় নিতে হবে?” তিনটি জায়গা, আর প্রতিটি বাদ দিলে আলাদা রকম ভুল হয়।

১ · শুরুর closure

শুরুর সেট {q0} ধরা, ECLOSE(q0) নয়। Eabc-তে তখন ε আর b, c-র মতো বৈধ log বাতিল হয়।

subset construction-এ

২ · প্রতিটি চিহ্নের পরের closure

move নিয়ে থেমে যাওয়া। Eabc-তে তখন ab বাতিল হয়, কারণ a-র পরে q1-এ যাওয়া হয় না।

simulation-এ

৩ · F′-এর বদল

ε-removal-এ F′ = F রেখে দেওয়া। তখন ε-এর উত্তর ভুল হয়, যদি শুরু থেকে ε-পথে accept state-এ যাওয়া যায়।

ε-removal-এ

এই ভুলগুলো ধরার সবচেয়ে নির্ভরযোগ্য উপায়, সঠিক আর ভুল রূপ দুটি পাশাপাশি চালিয়ে সব ছোট string-এ মেলানো। নিচের ব্লক অনুচ্ছেদ ১-এর union-যন্ত্রটি বানায়: নতুন শুরু s থেকে ε-তীরে parity যন্ত্রের p0 আর mod-3 যন্ত্রের r0. তারপর ε-removal তিনভাবে করে: সঠিকভাবে, F′ না বদলে, আর δ′-এর শুরুর closure বাদ দিয়ে। প্রতিবার দৈর্ঘ্য 10 পর্যন্ত সব binary string-এ language-এর সংজ্ঞার সঙ্গে মেলায়, আর shortlex ক্রমে প্রথম অমিলটি, অর্থাৎ সবচেয়ে ছোট counterexample, ছাপে।

from itertools import product
# s -eps-> p0 (even number of 1s), s -eps-> r0 (binary value divisible by 3)
delta = {(f"r{i}", b): {f"r{(2 * i + int(b)) % 3}"} for i in range(3) for b in "01"}
delta |= {(f"p{i}", b): {f"p{(i + int(b)) % 2}"} for i in range(2) for b in "01"}
eps = {"s": {"p0", "r0"}}
Q, start, F = ["s", "p0", "p1", "r0", "r1", "r2"], "s", {"p0", "r0"}
def eclose(S):
    seen, todo = set(S), list(S)
    while todo:
        new = eps.get(todo.pop(), set()) - seen
        seen |= new; todo += new
    return seen
def remove_eps(close_first=True, fix_F=True):
    d2 = {}
    for q in Q:
        C = eclose({q}) if close_first else {q}
        for a in "01":
            d2[q, a] = eclose({r for p in C for r in delta.get((p, a), ())})
    F2 = {q for q in Q if eclose({q}) & F} if fix_F else set(F)
    return d2, F2
def accepts(d2, F2, w):               # plain NFA run: no epsilon left
    S = {start}
    for a in w:
        S = {r for p in S for r in d2[p, a]}
    return bool(S & F2)
L = lambda w: w.count("1") % 2 == 0 or int(w or "0", 2) % 3 == 0
words = ["".join(t) for n in range(11) for t in product("01", repeat=n)]
for label, kw in [("correct", {}), ("F not fixed", {"fix_F": False}),
                  ("no closure first", {"close_first": False})]:
    d2, F2 = remove_eps(**kw)
    bad = [w for w in words if accepts(d2, F2, w) != L(w)]
    extra = f"  shortest={bad[0]!r}" if bad else ""
    print(f"{label:16} F'={sorted(F2)}  mismatches={len(bad)}{extra}")
d2, _ = remove_eps()
print("new row of s:  0 ->", sorted(d2["s", "0"]), "  1 ->", sorted(d2["s", "1"]))

আসল আউটপুট (ব্রাউজারের Python):

correct          F'=['p0', 'r0', 's']  mismatches=0
F not fixed      F'=['p0', 'r0']  mismatches=1  shortest=''
no closure first F'=['p0', 'r0', 's']  mismatches=1185  shortest='0'
new row of s:  0 -> ['p0', 'r0']   1 -> ['p1', 'r1']

সঠিক রূপে 2047টি string-এ অমিল 0, আর s নিজেই accept হয়েছে, কারণ ECLOSE(s) = {s, p0, r0}-এ দুটি accept state. F′ না বদলালে ভুল ঠিক একটি string-এ: খালি string, যা উপপাদ্য ১১.২-এর ধাপ ৫-এর ভবিষ্যদ্বাণী। এমন ভুল হাতে-পরীক্ষায় সহজে চোখ এড়িয়ে যায়, কারণ অশূন্য string-এ যন্ত্রটি নিখুঁত। শুরুর closure বাদ দিলে ক্ষতি বিশাল: s-এর নিজের কোনো চিহ্ন-তীর নেই, তাই δ′(s, a) = ∅, আর প্রতিটি অশূন্য string বাতিল। 2047টির মধ্যে 1185টি ভুল, আর প্রথমটি "0", যাতে 1 নেই, তাই parity পরীক্ষায় পাস করার কথা। শেষ লাইন দেখায়, সঠিক s-সারি আসলে দুই যন্ত্রের শুরুর সারি একসঙ্গে, পর্ব ০৯-এর ε-ছাড়া union-এর নিয়মের মতোই।

সতর্কতা: হাতে হিসাবের সময়। পরীক্ষার খাতায় subset construction করতে গিয়ে প্রতিটি নতুন সেটের পাশে একটি ছোট প্রশ্ন লিখে রাখুন: “এটি কি ε-বদ্ধ?” যদি কোনো সেটের একটি state থেকে ε-তীর বেরিয়ে সেটের বাইরে যায়, তবে closure নেওয়া হয়নি। আর শুরুতে, কোনো চিহ্ন পড়ার আগেই, ECLOSE(q0) লিখে ε-এর উত্তর ঠিক করে নিন।

৮ · বড় ছবি — ε কেন টিকে আছে, আর ইতিহাস

তিনটি যন্ত্র এখন একই শ্রেণির language চেনে, আর রূপান্তরের পথও জানা: ε-NFA থেকে ε-removal দিয়ে NFA (state একই), NFA থেকে subset construction দিয়ে DFA (state 2|Q| পর্যন্ত), আর DFA তো নিজেই একটি ε-ছাড়া NFA. তাহলে ε কেন রাখা? কারণ ε-NFA নির্মাণের ভাষা। Regular language-এর closure property-গুলো (পর্ব ১৬) প্রমাণ করতে, regex থেকে automaton বানাতে (পর্ব ১৪), আর lexer generator-এ অনেকগুলো token-এর যন্ত্র এক করতে (পর্ব ২২) ε-তীর সবচেয়ে সহজ আঠা। কাজ শেষে ε সরিয়ে বা DFA বানিয়ে দ্রুত চালানোর রূপ নেওয়া হয়।

যন্ত্রδ-এর রূপশুরুর সেটভালো কাজে
DFAQ × Σ → Qq0দ্রুত চালানো, complement, minimization
NFAQ × Σ → P(Q){q0}ছোট নকশা, guess and verify
ε-NFAQ × Σε → P(Q)ECLOSE(q0)যন্ত্র জোড়া, regex থেকে নির্মাণ

Thompson construction-এর ছক এখানে এক লাইনে বলি, পুরো নির্মাণ পর্ব ১৪-এ: regex-এর প্রতিটি অংশের জন্য একটি শুরু আর একটি accept state-এর ছোট টুকরো, আর union, concatenation ও star-এর জন্য ছবি ১১.১-এর মতো ε-তীর। ফলে যন্ত্রে প্রচুর ε থাকে, আর closure হিসাব হয়ে দাঁড়ায় regex engine-এর সবচেয়ে বেশি চলা অংশগুলোর একটি।

ε-move সহ finite automaton আর তাদের রূপান্তর এখন প্রায় সব পাঠ্যবইয়ের মানক বিষয়। Ken Thompson ১৯৬৮ সালে Communications of the ACM-এ “Regular Expression Search Algorithm” প্রবন্ধে regex থেকে যন্ত্র বানিয়ে সেট ধরে চালানোর পদ্ধতি দেখান; পাঠ্যবইয়ে যে রূপটি “Thompson construction” নামে শেখানো হয়, তাতে ε-তীর মূল আঠা। ε-move-এর ধারণা প্রথম কে আনুষ্ঠানিকভাবে সংজ্ঞায়িত করেন, সে বিষয়ে আমরা একটি নির্ভরযোগ্য একক সূত্র পাইনি, তাই এখানে কোনো একক নাম দিচ্ছি না। আজকের পাঠ্যবইয়ের দুটি মানক উপস্থাপনা হলো Sipser-এর E(R) আর Hopcroft–Motwani–Ullman-এর ECLOSE.

আরও গভীরে। ε-তীরের graph-এ একই strongly connected component-এর সব state-এর closure সমান (যেমন ECLOSE(q1) = ECLOSE(q3)), তাই Tarjan-এর মতো SCC algorithm দিয়ে প্রথমে প্রতিটি ε-চক্রকে একটি state-এ গুটিয়ে নিলে বাকি কাজ একটি চক্রহীন graph-এ হয় (DSA কোর্সের পর্ব ৪৬)। আরেক দিক থেকে, regex থেকে সরাসরি ε-ছাড়া NFA-ও বানানো যায়: position automaton (সাধারণত Glushkov আর McNaughton–Yamada-র নামে পরিচিত) m টি চিহ্ন-অবস্থানের regex-এ m + 1টি state দেয়, ε ছাড়াই। আর ε-removal-এর ঠিক এক জাতের কাজ পরে CFG-তে ফিরে আসবে: ε-production আর unit production দূর করা (পর্ব ২৮), যেখানে “nullable” nonterminal-এর হিসাব আসলে একই রকম closure.

পরীক্ষা ও ইন্টারভিউতে। এই প্রশ্নগুলো প্রায়ই আসে:

  • “প্রতিটি state-এর ε-closure লিখুন” — প্রতিটি state নিজেকে দিয়ে শুরু করুন, তারপর শুধু ε-তীর ধরে BFS; চক্রে seen দেখে থামুন।
  • “এই ε-NFA-কে DFA-তে রূপ দিন” — শুরু ECLOSE(q0); প্রতিটি সেট আর চিহ্নে move, তারপর closure; ∅ এলে dead state; যে সেটে F-এর state আছে, সেটি accept.
  • “ε-transition দূর করুন” — δ′(q, a) = ECLOSE(move(ECLOSE(q), a)), আর F′-এ যোগ করুন সেই q, যার closure-এ accept state আছে।
  • “ε-NFA কি DFA-র চেয়ে শক্তিশালী?” — না; তিনটিই ঠিক regular language চেনে, পার্থক্য শুধু আকার আর সুবিধায়।

৯ · AI-এর যুগে — ε-NFA-র রূপান্তর যাচাই

ε-NFA-র রূপান্তর AI সহকারীর কাছে একটি প্রিয় “ধাপে ধাপে” কাজ, আর উত্তর দেখতে গোছানো লাগে। কিন্তু closure-এর তিনটি জায়গার যেকোনো একটিতে ছোট একটি বাদ পড়লে টেবিল দেখতে ঠিকই থাকে, শুধু কয়েকটি string-এর উত্তর ভুল হয়। ভালো খবর: ε-NFA-কে Python dict-এ লিখে সব ছোট string-এ মূল যন্ত্র আর রূপান্তরিত যন্ত্র পাশাপাশি চালানো কয়েক মিনিটের কাজ।

AI-এর ভুলকেন ভুলযাচাইয়ের উপায়
DFA-র শুরু {q0}শুরুর closure বাদε আর এক চিহ্নের string আলাদা পরীক্ষা
ECLOSE(q)-তে q নিজে নেই“শূন্য ধাপ” ভুলে যাওয়াযেকোনো state-এর closure-এ সে নিজে আছে কি না দেখুন
শুধু এক ধাপের ε-তীর নেওয়াclosure মানে শূন্য বা বেশি ধাপদুই ধাপের ε-শিকল দিয়ে পরীক্ষা
ε-removal-এ F′ = Fখালি string-এর উত্তর ভুলসবসময় "" দিয়ে মূল আর নতুন যন্ত্র মেলান
DFA-তে ε কলাম রেখে দেওয়াDFA-র alphabet Σ, Σε নয়টেবিলের কলামগুলো গুনুন
“ε-NFA বেশি শক্তিশালী”উপপাদ্য ১১.১ উল্টো কথা বলেপর্ব ১০ আর এই পর্বের প্রমাণ দেখুন
বানানো রেফারেন্স বা সালউৎস হয়তো নেইSipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে দেখুন

নিচের prompt-টি AI-কে এমন আকারে উত্তর দিতে বাধ্য করে, যা আপনি সরাসরি চালিয়ে যাচাই করতে পারেন: প্রতিটি closure আলাদা, প্রতিটি সারির move আর closure আলাদা, আর একটি brute-force তুলনা।

আমি গণনার তত্ত্ব শিখছি। Σ = {0, 1}-এর ওপর একটি ε-NFA: state q0, q1, q2, q3; শুরু q0; F = {q3}; ε-তীর q0→q1, q2→q0, q3→q1; চিহ্ন-তীর δ(q0,1) = {q0}, δ(q1,0) = {q2}, δ(q2,1) = {q3}; বাকি কোনো তীর নেই। ১. প্রতিটি state-এর ε-closure দাও, BFS-এর queue-সহ। ২. Subset construction দিয়ে DFA বানাও: শুরুর state কী এবং কেন, প্রতিটি সারিতে move আর তারপর closure আলাদা করে লেখো, ∅ এলে স্পষ্ট বলো। ৩. ε-removal করে ε-ছাড়া NFA দাও: δ′ টেবিল আর F′, প্রতিটি F′-সদস্যের কারণসহ। ৪. খালি string, "01", "011", "0101" তিন যন্ত্রেই গৃহীত কি না দেখাও। ৫. শুধু standard library দিয়ে একটি Python পরীক্ষা লেখো, যা দৈর্ঘ্য 10 পর্যন্ত সব string-এ মূল ε-NFA, তোমার DFA আর তোমার NFA-কে মেলায় আর অমিল ছাপে। কোনো বইয়ের উল্লেখ করলে বইয়ের নাম আর অধ্যায় দাও; নিশ্চিত না হলে বলো "নিশ্চিত নই"।

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

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১ε-transition কোনো নতুন language আনে না। তাহলে সংজ্ঞাটি জটিল করে ε রাখার যুক্তি কী?

যুক্তিটি মডুলার নির্মাণ। গণিতে আর প্রকৌশলে বড় জিনিস ছোট ছোট টুকরো জুড়ে বানানো হয়, আর টুকরো জোড়ার নিয়ম যত সরল, পুরো নির্মাণের প্রমাণ তত সহজ। ε-তীর এমন একটি জোড়া, যা কোনো টুকরোর ভেতরে হাত দেয় না। Union-এ নতুন শুরু থেকে দুটি ε; concatenation-এ প্রথম যন্ত্রের accept থেকে দ্বিতীয়টির শুরুতে ε; star-এ accept থেকে শুরুতে ফেরার ε আর একটি নতুন শুরু, যা নিজে accept. প্রতিটি নির্মাণের সঠিকতা এক অনুচ্ছেদে প্রমাণ হয়, কারণ পুরোনো যন্ত্রগুলোর তীর অপরিবর্তিত।

ε ছাড়া একই কাজ করা যায়, কিন্তু প্রতিটি জোড়ায় ভেতরের সারি নকল করতে হয়। পর্ব ০৯-এর ε-ছাড়া union-এ নতুন শুরুর সারি ছিল দুই যন্ত্রের শুরুর সারির union, আর s accept কি না তা আলাদা করে ঠিক করতে হয়েছিল। Concatenation-এ প্রথম যন্ত্রের প্রতিটি accept state-এর সারিতে দ্বিতীয় যন্ত্রের শুরুর সারি যোগ করতে হয়, আর দ্বিতীয় যন্ত্র ε গ্রহণ করলে প্রথম যন্ত্রের accept state-গুলোকেও accept রাখতে হয়। এই প্রতিটি বিশেষ ক্ষেত্র ভুলের সম্ভাব্য উৎস। ε-removal আসলে ঠিক এই বিশেষ ক্ষেত্রগুলো যান্ত্রিকভাবে, একবারে, সঠিকভাবে করে দেয়।

একটি খরচও আছে, আর সেটি সৎভাবে বলা দরকার। Thompson-ধাঁচের নির্মাণে regex-এর দৈর্ঘ্যের অনুপাতে state থাকে, কিন্তু অনেক ε-তীর জমে যায়। এগুলো সরালে state-সংখ্যা একই থাকে, কিন্তু তীর বেড়ে |Q|2 · |Σ|-এর কাছাকাছি যেতে পারে। তাই বাস্তব tool অনেক সময় ε রেখেই চালায় আর closure-এর হিসাব cache করে, অথবা position automaton-এর মতো এমন নির্মাণ নেয়, যেখানে ε প্রথম থেকেই আসে না।

এই প্যাটার্নটি কম্পিউটার বিজ্ঞানে বারবার দেখা যায়: একটি মধ্যবর্তী রূপ (intermediate representation), যা মানুষ ও প্রমাণের জন্য সহজ, তারপর একটি যান্ত্রিক রূপান্তর, যা চালানোর জন্য দ্রুত রূপ দেয়। Compiler-এর IR, database-এর query plan, আর ε-NFA একই পরিবারের সদস্য।

মূল উপলব্ধি: ε-NFA শক্তি নয়, নির্মাণের সুবিধা দেয়। জটিলতা সংজ্ঞায় একবার রাখা হয়, যাতে প্রতিটি নির্মাণ আর প্রমাণ সরল থাকে, আর রূপান্তর সেই জটিলতা শেষে যান্ত্রিকভাবে সরিয়ে দেয়।

প্র ০২ε-closure আসলে graph-এর reachability. তাহলে সব state-এর closure একসঙ্গে বের করার সবচেয়ে ভালো উপায় কী?

উত্তর নির্ভর করে যন্ত্রের আকার আর কতবার closure লাগবে তার ওপর। সরল পথ: প্রতিটি state থেকে আলাদা BFS. একটি BFS-এ O(|Q| + e) সময়, যেখানে e হলো ε-তীরের সংখ্যা, তাই সব state-এর জন্য O(|Q| · (|Q| + e)). পরীক্ষার খাতার ছোট যন্ত্রে এটিই যথেষ্ট, আর ভুলের সম্ভাবনাও সবচেয়ে কম।

দ্বিতীয় পথ Warshall-এর algorithm, যা Stephen Warshall ১৯৬২ সালে প্রকাশ করেন। এটি একটি relation-এর transitive closure বের করে O(|Q|3) সময়ে, একটি |Q| × |Q| boolean matrix-এ তিনটি nested loop দিয়ে। ε-relation-এ এটি চালিয়ে কর্ণের ঘরগুলো সত্য করে দিলেই reflexive-transitive closure, অর্থাৎ সব ECLOSE একসঙ্গে। ঘন graph-এ, যেখানে ε-তীর অনেক, এর সরল কাঠামো সুবিধাজনক; বিরল graph-এ BFS দ্রুততর। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৪-এ algorithm-টি ধাপে ধাপে আছে।

তৃতীয় পথ চক্রগুলোকে কাজে লাগানো। একই strongly connected component-এর সব state-এর closure সমান, কারণ তারা পরস্পরের কাছে বিনা খরচে যেতে পারে। তাই প্রথমে Tarjan-এর algorithm-এর মতো রৈখিক সময়ের SCC algorithm দিয়ে প্রতিটি component-কে একটি বিন্দুতে গুটিয়ে নেওয়া যায়; তখন graph চক্রহীন হয়, আর topological ক্রমের উল্টো দিক থেকে closure-গুলো আগেরগুলো জুড়ে গড়ে তোলা যায়। চক্রহীনতার আরেকটি লাভ: ε-চক্র থাকলে কোনো সরল recursive program অসীম loop-এ পড়তে পারে, গুটিয়ে নিলে সেই ঝুঁকি থাকে না।

বাস্তবের regex engine প্রায়ই একটি চতুর্থ পথ নেয়: সব closure আগে থেকে না বানিয়ে, প্রতিটি চিহ্নের পর যে সেটটি দরকার, শুধু সেটির closure হিসাব করে, আর একটি “এই ধাপে ইতিমধ্যে যোগ হয়েছে” চিহ্ন দিয়ে পুনরাবৃত্তি এড়ায়। এটি আমাদের BFS-এর seen সেটেরই রূপ।

মূল উপলব্ধি: ECLOSE নতুন কোনো জাদু নয়; এটি graph তত্ত্বের পুরোনো reachability প্রশ্ন। কোন algorithm ভালো, তা graph কত ঘন, চক্র আছে কি না, আর closure কতবার লাগবে তার ওপর নির্ভর করে।

প্র ০৩Regex engine-এর ভেতরে ε-তীর কোথায় লুকিয়ে থাকে, আর ε-চক্র সেখানে কী বিপদ ডাকতে পারে?

Thompson-ধাঁচের নির্মাণে regex-এর প্রায় প্রতিটি operator ε-তীর তৈরি করে। x|y-এর জন্য একটি নতুন শুরু থেকে দুটি ε; x*-এর জন্য পুনরাবৃত্তি শুরুতে ফেরার ε আর শূন্যবার মেলার জন্য পাশ কাটানোর ε. ফলে একটি সাধারণ pattern-এর যন্ত্রেও state-এর বড় অংশ শুধু ε-তীরের সংযোগস্থল। সেট ধরে যে engine চলে, সে প্রতিটি চিহ্নের পর ঠিক এই পর্বের ECLOSE(move(S, a)) হিসাব করে; Russ Cox-এর ২০০৭ সালের “Regular Expression Matching Can Be Simple And Fast” প্রবন্ধে এই পদ্ধতি সহজ ভাষায় বর্ণিত, যেখানে closure-এর কাজ করে নতুন state যোগ করার একটি ছোট recursive ফাংশন।

বিপদ আসে ε-চক্র থেকে। (a*)*-এর মতো pattern-এ ভেতরের অংশ খালি string মেলাতে পারে, তাই বাইরের star-এর loop কোনো চিহ্ন না পড়েই আবার শুরুতে ফিরতে পারে: একটি ε-চক্র। সেট-পদ্ধতির engine এতে বিপদে পড়ে না, কারণ seen সেট চক্র থামায়, ঠিক stepper-এর ধাপ ৫-এর মতো। কিন্তু backtracking engine, যে একটি একটি পথ চেষ্টা করে, সতর্ক না থাকলে একই খালি পুনরাবৃত্তি বারবার নিতে পারে। এজন্য বাস্তব backtracking engine-গুলো সাধারণত একটি নিয়ম রাখে, যেমন “একটি পুনরাবৃত্তি যদি কোনো চিহ্ন না খায়, তবে loop আর ঘুরবে না”। নিয়মের খুঁটিনাটি engine-ভেদে আলাদা, তাই নির্দিষ্ট engine-এর আচরণ তার নিজের documentation-এ দেখে নেওয়াই নিরাপদ।

আরেকটি সমস্যা গতির। Nested quantifier-এ backtracking engine-এর পথের সংখ্যা exponential হতে পারে, যার নিরাপত্তা-রূপ ReDoS. পর্ব ২১-এ নিজের computer-এ ছোট input দিয়ে নিরাপদভাবে এর সময় মাপা হবে। সেট-পদ্ধতিতে closure-এর খরচ প্রতিটি চিহ্নে বড়জোর state আর তীরের সংখ্যার অনুপাতে, তাই মোট সময় input-এর দৈর্ঘ্যে রৈখিক থাকে।

মূল উপলব্ধি: ε-closure regex engine-এর ভেতরের সবচেয়ে বেশি চলা ফাংশনগুলোর একটি। seen সেট দিয়ে চক্র থামানো শুধু পরীক্ষার খাতার নিয়ম নয়; বাস্তব engine-এর সঠিকতা আর গতি দুটিই এর ওপর দাঁড়ায়।

প্র ০৪Finite automaton-এ ε-move সরানো যায়। Stack-সহ যন্ত্রেও কি তাই?

উত্তর যন্ত্রভেদে আলাদা, আর পার্থক্যটি শিক্ষণীয়। Finite automaton-এ ε-move সরানো যায়, কারণ ε-লাফে যন্ত্রের একমাত্র স্মৃতি, state, শুধু একটি সসীম graph-এ নড়ে; সেই graph-এর reachability আগে থেকে হিসাব করে নতুন তীরে ভরে দেওয়া যায়। এই পর্বের পুরো কৌশল এটুকুই।

Pushdown automaton-এ (stack-সহ যন্ত্র, পর্ব ৩২) ε-move চিহ্ন না পড়েই stack বদলাতে পারে, যেমন অনেকগুলো চিহ্ন একসঙ্গে সরিয়ে ফেলা। এখানে nondeterministic PDA-র জন্য খবর ভালো: প্রতিটি context-free language-এর একটি Greibach normal form grammar আছে (Sheila Greibach, ১৯৬৫), যেখানে প্রতিটি rule একটি terminal দিয়ে শুরু হয়। এমন grammar থেকে যে PDA বানানো হয়, তা প্রতিটি ধাপে একটি করে চিহ্ন পড়ে; অর্থাৎ খালি string-এর বিশেষ ক্ষেত্রটি বাদে nondeterministic PDA থেকেও ε-move সরানো যায় (পর্ব ৩০ আর ৩৪)।

Deterministic PDA-তে চিত্র আলাদা। সাহিত্যে একটি সুপরিচিত ফল হলো, যে deterministic PDA কখনো ε-move নেয় না (একে “real-time” বলা হয়), তা সব deterministic context-free language চেনে না। অর্থাৎ deterministic জগতে ε-move সত্যিকারের ক্ষমতা যোগ করে: চিহ্ন না পড়ে stack পরিষ্কার করার সুযোগ ছাড়া কিছু কাজ করা যায় না। এর প্রমাণ এই কোর্সের আওতার বাইরে; পর্ব ৩৫-এ deterministic PDA-র মূল ধারণাগুলো আসবে।

Turing machine-এ “ε-move” সরাসরি অর্থবহ নয়, কারণ যন্ত্রটি tape থেকে পড়ে আর head যেকোনো দিকে নড়ে; তবু একটি সমতুল্য প্রশ্ন আছে, head না নড়িয়ে থাকার ধাপ, যা সহজেই সরানো যায় (পর্ব ৪৫-এর রূপভেদ)। Output-সহ যন্ত্রে (পর্ব ১২) আবার ε output, অর্থাৎ কিছু না লেখা, একটি আলাদা বিষয়।

মূল উপলব্ধি: “ε সরানো যায় কি না” প্রশ্নের উত্তর নির্ভর করে ε-লাফে যন্ত্রের কতটুকু স্মৃতি বদলাতে পারে তার ওপর। শুধু সসীম state বদলালে সরানো সহজ; অসীম stack বদলালে deterministic জগতে ε সত্যিকারের ক্ষমতা।

প্র ০৫Closure ভুলে যাওয়ার ভুল এত সাধারণ কেন, আর program লেখার সময় এর বিরুদ্ধে সবচেয়ে ভালো প্রতিরক্ষা কী?

ভুলটি সাধারণ, কারণ এটি একটি অদৃশ্য ধাপ। DFA আর NFA-তে প্রতিটি পরিবর্তন একটি চিহ্নের সঙ্গে আসে, তাই চিহ্ন গুনে হিসাব মেলানো যায়। ε-লাফ কোনো চিহ্নের সঙ্গে আসে না, তাই মন তাকে সহজে বাদ দেয়, বিশেষ করে শুরুতে, যখন এখনো কিছুই পড়া হয়নি। আরেকটি কারণ: ভুল প্রায়ই খুব অল্প string-এ ধরা পড়ে। Pyodide ব্লকে F′ না বদলানোর ভুল 2047টি string-এর মধ্যে মাত্র একটিতে, খালি string-এ, দেখা দিয়েছিল। হাতে বাছা কয়েকটি “সাধারণ” উদাহরণে এমন ভুল প্রায় কখনো ধরা পড়ে না।

প্রথম প্রতিরক্ষা একটি invariant: “আমার program-এর প্রতিটি state-সেট সবসময় ε-বদ্ধ।” এটিকে কোডে লিখে রাখা যায়, যেমন প্রতিটি ধাপের পরে assert eclose(S) == S. পর্ব ০৪-এর প্রমাণের ভাষায়, এটি একটি inductive invariant: শুরুতে সত্য (কারণ শুরু ECLOSE(q0)), আর প্রতিটি ধাপ সেটিকে টিকিয়ে রাখে (কারণ move-এর পরে closure). উপপাদ্য ১১.২-এর প্রমাণ ঠিক এই invariant ব্যবহার করেছে।

দ্বিতীয় প্রতিরক্ষা differential testing: একই language-এর দুটি স্বাধীন রূপ, যেমন মূল ε-NFA-র সরাসরি simulation আর রূপান্তরিত DFA, সব ছোট string-এ পাশাপাশি চালানো। ব্লকগুলো ঠিক এটাই করেছে, আর shortlex ক্রমে খোঁজায় সবচেয়ে ছোট counterexample আপনা থেকেই আগে আসে। খালি string, এক চিহ্নের string আর সীমানার দৈর্ঘ্য এই তালিকার শুরুতেই থাকে, যেখানে closure-এর ভুল সবচেয়ে বেশি লুকায়।

তৃতীয় প্রতিরক্ষা এলোমেলো যন্ত্রে পরীক্ষা: একটি নির্দিষ্ট seed দিয়ে অনেক ছোট ε-NFA বানিয়ে প্রতিটিতে রূপান্তর আর তুলনা চালানো। এই ধারণাটি property-based testing নামে পরিচিত (সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮)। একটি নির্দিষ্ট উদাহরণ হয়তো ε-চক্র বা দুই ধাপের ε-শিকল রাখে না; শত শত এলোমেলো যন্ত্রের মধ্যে কোনো একটি রাখবেই।

মূল উপলব্ধি: অদৃশ্য ধাপের ভুল চোখে ধরা কঠিন, কিন্তু যন্ত্রে ধরা সহজ। একটি স্পষ্ট invariant আর সব ছোট string-এ দুই রূপের তুলনা মিলে closure-এর প্রায় সব ভুল কয়েক সেকেন্ডে বের করে দেয়।

অনুশীলন

একটি নকশা ও রূপান্তর, একটি trace, একটি ε-removal আর একটি প্রমাণ। আগে নিজে চেষ্টা করুন, তারপর উত্তর খুলুন।

  1. নকশা ও রূপান্তর: Σ = {0, 1}-এর ওপর L = 0∗1∗ ∪ 1∗0∗ (যেমন 0011, 1100, ε আছে; 010, 101 নেই)। ε-তীর দিয়ে একটি ε-NFA নকশা করুন, ECLOSE(শুরু) লিখুন, তারপর subset construction করে বলুন DFA-তে কয়টি state.

    দুটি টুকরো: a0 (0-র loop) থেকে ε-তীরে a1 (1-এর loop), F-এ a1; আর b0 (1-এর loop) থেকে ε-তীরে b1 (0-র loop), F-এ b1. নতুন শুরু s থেকে ε-তীরে a0 আর b0. মোট ৫টি state, F = {a1, b1}.

    ECLOSE(s) = {s, a0, a1, b0, b1}, এতে accept state আছে, তাই ε গৃহীত। Subset construction:

    DFA state01
    → ∗ {s, a0, a1, b0, b1}{a0, a1, b1}{a1, b0, b1}
    ∗ {a0, a1, b1}{a0, a1, b1}{a1}
    ∗ {a1, b0, b1}{b1}{a1, b0, b1}
    ∗ {a1}∅{a1}
    ∗ {b1}{b1}∅
    ∅∅∅

    ৬টি state, তার মধ্যে ৫টি accept আর ∅ dead state. দ্বিতীয় সারি পড়ুন: “এখন পর্যন্ত শুধু 0” অবস্থায় দুই সম্ভাবনাই খোলা (a-অংশে 0-র পর্ব বা b-অংশে 0-র পর্ব)। যাচাই: একটি scratch script দৈর্ঘ্য 10 পর্যন্ত সব string-এ ε-NFA-কে সংজ্ঞার সঙ্গে মিলিয়েছে, অমিল 0, আর একই script এই ৬টি সেটই দিয়েছে।

  2. Trace (আউটপুট অনুমান করুন): Σ = {0, 1}-এর ওপর ε-NFA: state q0–q3, শুরু q0, F = {q3}; ε-তীর q0 → q1, q2 → q0, q3 → q1; চিহ্ন-তীর δ(q0, 1) = {q0}, δ(q1, 0) = {q2}, δ(q2, 1) = {q3}. প্রতিটি state-এর ε-closure লিখুন, তারপর 0101 আর 011-এর trace করুন। যন্ত্রটি কোন language চেনে?

    ECLOSE(q0) = {q0, q1}, ECLOSE(q1) = {q1}, ECLOSE(q2) = {q0, q1, q2} (q2 → q0 → q1), ECLOSE(q3) = {q1, q3}.

    0101: শুরু {q0, q1} → 0: move {q2}, close {q0, q1, q2} → 1: move {q0, q3}, close {q0, q1, q3} → 0: move {q2}, close {q0, q1, q2} → 1: move {q0, q3}, close {q0, q1, q3}. শেষে q3 আছে, গৃহীত।

    011: শুরু {q0, q1} → 0: {q0, q1, q2} → 1: {q0, q1, q3} → 1: move {q0}, close {q0, q1}. q3 নেই, বাতিল।

    যন্ত্রটি চেনে “শেষ দুটি চিহ্ন 01”, অর্থাৎ পর্ব ০৯-এর L01. একটি scratch script দৈর্ঘ্য 12 পর্যন্ত সব string-এ এটি যাচাই করেছে, আর subset construction-এ এর DFA-তে ৩টি state আসে: {q0, q1}, {q0, q1, q2}, {q0, q1, q3}.

  3. ε-removal: অনুশীলন ২-এর ε-NFA থেকে সংজ্ঞা ১১.৬ দিয়ে ε-ছাড়া NFA বানান: δ′ টেবিল আর F′ লিখুন। Eabc-তে সব state accept হয়ে গিয়েছিল; এখানে F′ বদলায় কি না, আর কেন?
    stateECLOSE01
    → q0{q0, q1}{q0, q1, q2}{q0, q1}
    q1{q1}{q0, q1, q2}∅
    q2{q0, q1, q2}{q0, q1, q2}{q0, q1, q3}
    ∗ q3{q1, q3}{q0, q1, q2}∅

    উদাহরণ হিসেবে q2-এর 1-সারি: ECLOSE(q2) = {q0, q1, q2}; এদের 1-তীর δ(q0, 1) = {q0} আর δ(q2, 1) = {q3}, তাই move = {q0, q3}; তার closure {q0, q1, q3}.

    F′ = {q3}, বদলায়নি। কারণ শুধু q3-এর closure-এ q3 আছে; q0, q1, q2-এর কোনোটি থেকে ε-পথে q3-এ যাওয়া যায় না (q3-এ ঢোকার একমাত্র তীর একটি 1-তীর)। Eabc-তে উল্টো, সব state থেকে ε-পথে q2-এ যাওয়া যেত। F′ শুধু ε-পথের ওপর নির্ভর করে। যাচাই: একটি scratch script একই টেবিল দিয়েছে।

  4. প্রমাণ করুন: প্রতিটি ε-NFA E-এর জন্য এমন একটি ε-NFA E′ আছে, যাতে L(E′) = L(E), E′-এর accept state ঠিক একটি, আর সেই accept state থেকে কোনো তীর বের হয় না।

    Construction proof: E = (Q, Σ, δ, q0, F) থেকে একটি নতুন state f ∉ Q নিন। E′ = (Q ∪ {f}, Σ, δ′, q0, {f}), যেখানে δ′ হুবহু δ, শুধু প্রতিটি p ∈ F-এর জন্য δ′(p, ε) = δ(p, ε) ∪ {f}, আর f-এর সব ঘর ∅.

    1. (⊆) ধরুন w ∈ L(E′). তাহলে একটি পথ f-এ শেষ। f-এ ঢোকার একমাত্র তীর কোনো p ∈ F থেকে একটি ε-তীর, আর f থেকে কোনো তীর বের হয় না, তাই পথের শেষ ধাপটি p →ε f. — δ′-এর গঠন
    2. শেষ ধাপটি বাদ দিলে w-এর একটি পথ পাওয়া যায়, যা p ∈ F-এ শেষ, আর যার সব তীর E-এরও তীর। শেষ ধাপটি ε বলে w বদলায় না। তাই w ∈ L(E). — সংজ্ঞা ১১.২
    3. (⊇) ধরুন w ∈ L(E): একটি পথ কোনো p ∈ F-এ শেষ। এই পথ E′-এও বৈধ, কারণ δ ⊆ δ′. শেষে p →ε f জুড়ে দিলে w-এর একটি পথ f-এ শেষ হয়, তাই w ∈ L(E′). — সংজ্ঞা ১১.২ ∎

    পর্ব ০৯-এর একটি অনুশীলনে দেখেছিলেন, ε ছাড়া এমন রূপ সবসময় সম্ভব নয় (যেমন {ε, a}-এর জন্য)। ε থাকলে এটি দুই লাইনের নির্মাণ, আর Thompson construction-এর প্রতিটি টুকরো ঠিক এই আকারের।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি ε-NFA থেকে subset construction দিয়ে DFA বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি state-এর ε-closure হিসাব করা
  2. DFA-র শুরুর state হিসেবে ECLOSE(q0) নেওয়া
  3. একটি অপ্রক্রিয়াকৃত সেট S আর একটি চিহ্ন a নিয়ে move(S, a) বের করা
  4. move-এর ফলের ε-closure নিয়ে δD(S, a) লেখা, আর নতুন সেট হলে তালিকায় যোগ করা
  5. F-এর কোনো state আছে এমন প্রতিটি সেটকে accept state চিহ্নিত করা

একটি ε-NFA-তে ε-তীর শুধু তিনটি: q0 → q1, q1 → q2, আর q3 → q0. ECLOSE(q0) কী?

  • {q0, q1, q2}
  • {q1, q2}
  • {q0, q1, q2, q3}
  • {q0, q1}

ε-NFA E = (Q, Σ, δ, q0, F)-এর transition function-এর সঠিক রূপ কোনটি?

  • δ: Q × Σ → Q
  • δ: Q × Σ → P(Q)
  • δ: Q × Σε → P(Q)
  • δ: Q × Σε → Q

ε-NFA-তে state q0, q1, q2; শুরু q0; F = {q2}; δ(q0, a) = {q0}, δ(q1, b) = {q1}, δ(q2, c) = {q2}; ε-তীর q0 → q1 আর q1 → q2. Input ab পড়ার পর state-এর সেট কী?

  • {q1}
  • {q1, q2}
  • {q0, q1, q2}
  • ∅

ε-NFA থেকে subset construction-এ DFA-র শুরুর state কোনটি?

  • {q0}
  • Q
  • ECLOSE(F)
  • ECLOSE(q0)

ε-NFA থেকে একই state-এর ε-ছাড়া NFA বানাতে (δ′(q, a) = ECLOSE(move(ECLOSE(q), a)) নিয়ে) নতুন accept সেট F′ কী হবে?

  • যেসব q-এর ECLOSE(q)-তে F-এর কোনো state আছে
  • শুধু F, কোনো বদল নয়
  • ECLOSE(F)
  • Q-এর সব state

ε-NFA, ε-ছাড়া NFA আর DFA-র চেনার ক্ষমতা সম্পর্কে কোন বক্তব্যটি সঠিক?

  • ε-NFA কিছু non-regular language চেনে
  • ε-ছাড়া NFA ε-NFA-র চেয়ে দুর্বল
  • তিনটিই ঠিক একই শ্রেণি, regular language চেনে
  • DFA সবচেয়ে দুর্বল, কারণ তাতে nondeterminism নেই

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. E = (Q, Σ, δ, q0, F), δ: Q × Σε → P(Q). ε-তীরে চিহ্ন না পড়েই যাওয়া যায়; জোড়া লাগানোর সবচেয়ে সহজ আঠা।
  2. ECLOSE(q) = শূন্য বা বেশি ε-ধাপে পৌঁছানোর সব state, q নিজেসহ; BFS-এ O(|Q| + e), seen সেট চক্র থামায়।
  3. শুরুতে closure, প্রতিটি চিহ্নের পরে closure: δ̂(q, wa) = ECLOSE(move(δ̂(q, w), a)); DFA-র শুরু ECLOSE(q0).
  4. ε-removal: δ′(q, a) = ECLOSE(move(ECLOSE(q), a)), F′ = {q : ECLOSE(q) ∩ F ≠ ∅}; state একই, তীর বাড়তে পারে।
  5. শক্তি সমান, যাচাই জরুরি। ε-NFA = NFA = DFA = regular; closure-এর ভুল প্রায়ই শুধু খালি বা খুব ছোট string-এ ধরা পড়ে, তাই সব ছোট string-এ তুলনা করুন।

পরের পর্বে: এতক্ষণ যন্ত্র শুধু “হ্যাঁ” বা “না” বলেছে। এবার যন্ত্র প্রতিটি ধাপে কিছু লিখবেও: Mealy আর Moore machine, বাজারঘরের checkout যন্ত্রের বার্তা আর বিট ধরে দুটি binary সংখ্যা যোগ করার যন্ত্র।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান