এই পর্বে যা শিখবেন
- DFA-র ৫-tuple সংজ্ঞার প্রতিটি অংশ, আর “deterministic” ও “total” শব্দ দুটির সঠিক মানে
- State diagram আর transition table পড়া ও একটি থেকে অন্যটি বানানো
- Extended transition function δ̂-এর inductive সংজ্ঞা, আর তার একটি মৌলিক lemma-র প্রমাণ
- L(M), regular language-এর সংজ্ঞা, dead state, সম্পূর্ণ DFA আর unreachable state
- DFA-কে একটি লুপ হিসেবে লেখা, linear-time membership, ADFA-এর decidability আর DFA গোনার সূত্র, সবই Python ও JavaScript-এ চালিয়ে যাচাই
১ · সসীম স্মৃতি — একটি যন্ত্র কতটুকু মনে রাখে
মেট্রো রেলের স্টেশনে ঢোকার গেটটি ভাবুন। গেট দুই অবস্থার যেকোনো একটিতে থাকে: “বন্ধ” বা “খোলা”। কার্ড ছোঁয়ালে বন্ধ গেট খোলে; খোলা গেটে একজন ধাক্কা দিয়ে ঢুকলে আবার বন্ধ হয়। গেটটি জানে না আজ কতজন ঢুকেছেন, কে কখন কার্ড ছুঁয়েছেন। তার পুরো স্মৃতি একটিই তথ্য: এখন সে কোন অবস্থায়। পরের ঘটনায় কী করবে, তা ঠিক করে শুধু এই অবস্থা আর ঘটনাটি।
এই “অবস্থা”-ই state. লিফটের প্যানেলও একই রকম: “এখন কোন তলায়, কোন দিকে যাচ্ছে” জানলেই পরের বোতাম চাপায় কী হবে বলা যায়। মোবাইল ব্যাংকিংয়ের PIN মেনুতে যন্ত্রকে শুধু মনে রাখতে হয় এ পর্যন্ত কয়টি অঙ্ক টাইপ হয়েছে (০, ১, ২, ৩ বা ৪), আর ভুল চিহ্ন এসেছে কি না। আগের অঙ্কগুলো পুরোপুরি মনে রাখার দরকার নেই, যদি প্রশ্নটি শুধু “চার অঙ্ক হয়েছে কি না” হয়।
গণনার তত্ত্বে এই ধারণার সবচেয়ে সরল গাণিতিক রূপ হলো finite automaton. পর্ব ০১-এ (গণনার তত্ত্বের মানচিত্র) আপনি একটি ছোট state machine চালিয়েছেন, আর ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৪ DFA, NFA আর regex-এর একটি পরিচয় দেয়। এই পর্ব সেই ভিত্তির ওপর নিখুঁত সংজ্ঞা, প্রমাণ আর হিসাব দেবে। নোটেশন পর্ব ০৩-এর (Alphabet, string আর language) মতোই: Σ সসীম, অশূন্য alphabet; ε ফাঁকা string (কিছু বইয়ে λ); |w| দৈর্ঘ্য; Σ∗ সব string-এর সেট।
Finite automaton-এর তিনটি বৈশিষ্ট্য মনে রাখুন, কারণ পুরো মডিউল এদের ওপর দাঁড়িয়ে:
- এক দিকে, একবার পড়া: ইনপুট বাঁ থেকে ডানে একটি করে চিহ্ন পড়া হয়; পেছনে ফেরা বা আগে লাফ দেওয়া নেই।
- সসীম স্মৃতি: state-এর সংখ্যা নির্দিষ্ট আর সসীম, ইনপুট যত লম্বাই হোক। কোনো খাতা, stack বা tape নেই।
- শেষে হ্যাঁ বা না: পড়া শেষে যন্ত্র যে state-এ থামে, সেটি “গ্রহণ” তালিকায় থাকলে string গৃহীত, নইলে বাতিল।
“Deterministic” শব্দের মানে: কোনো state-এ কোনো চিহ্ন পড়লে পরের state ঠিক একটি, কোনো বিকল্প নেই, কোনো অনুমান নেই। একই ইনপুটে একই যন্ত্র সবসময় একই পথে চলে। পর্ব ০৯-এ এই শর্ত তুলে দিয়ে NFA আসবে, যেখানে একসঙ্গে অনেক পথ থাকে।
২ · Formal definition — পাঁচটি অংশের একটি tuple
একটি deterministic finite automaton হলো একটি ৫-tuple M = (Q, Σ, δ, q0, F), যেখানে
- Q একটি সসীম সেট, যার সদস্যদের বলি state;
- Σ একটি সসীম, অশূন্য সেট, ইনপুটের alphabet;
- δ: Q × Σ → Q হলো transition function, যা প্রতিটি জোড় (state, চিহ্ন)-কে ঠিক একটি state দেয়;
- q0 ∈ Q হলো start state;
- F ⊆ Q হলো accepting state-এর সেট (final state-ও বলা হয়)।
প্রতিটি অংশ একটি করে প্রশ্নের উত্তর: যন্ত্রের কয়টি অবস্থা (Q), সে কোন চিহ্ন পড়তে পারে (Σ), প্রতিটি অবস্থায় প্রতিটি চিহ্নে কী করে (δ), কোথা থেকে শুরু (q0), আর কোথায় থামলে “হ্যাঁ” (F), এই পাঁচটি প্রশ্নের উত্তরেই যন্ত্রটি পুরো বর্ণিত হয়। কয়েকটি সূক্ষ্ম কথা পরীক্ষায় প্রায়ই ধরা হয়:
- δ একটি total function: Q × Σ-এর প্রতিটি জোড়ে δ সংজ্ঞায়িত। তাই |Q| = n আর |Σ| = k হলে transition ঠিক nkটি। কোনো তীর “ভুলে যাওয়া” চলে না (§৬)।
- F ফাঁকা হতে পারে: তখন যন্ত্র কিছুই গ্রহণ করে না, L(M) = ∅. আবার F = Q হলে সব string গৃহীত, L(M) = Σ∗.
- q0 ∈ F হতে পারে: তখন ফাঁকা string ε গৃহীত, কারণ কিছু না পড়েই যন্ত্র accepting state-এ আছে।
- State-এর নাম অর্থহীন: q0, q1 বা “জোড়”, “বিজোড়”, যেকোনো নাম চলে; গুরুত্বপূর্ণ শুধু transition-এর গঠন।
প্রথম উদাহরণ বাজারঘরের গুদাম থেকে। একটি সেন্সর লাইন একটির পর একটি বিট দেয়, আর (কাল্পনিক) parity check-এর নিয়ম: একটি বৈধ বার্তায় 1-এর সংখ্যা জোড়। Language PAR = {w ∈ {0, 1}∗ : w-এ 1-এর সংখ্যা জোড়}. যন্ত্রকে শুধু মনে রাখতে হয় “এ পর্যন্ত 1-এর সংখ্যা জোড় না বিজোড়”। তাই দুটি state যথেষ্ট:
MPAR = ({E, O}, {0, 1}, δ, E, {E})
এখানে E মানে “even, এ পর্যন্ত জোড় সংখ্যক 1” আর O মানে “odd, বিজোড় সংখ্যক 1” পড়া হয়েছে। δ(E, 0) = E, δ(E, 1) = O, δ(O, 0) = O, δ(O, 1) = E: 0 পড়লে কিছু বদলায় না, 1 পড়লে জোড়-বিজোড় উল্টে যায়।
Parity DFA-র state diagram
বাঁয়ের খোলা তীর start state দেখায়। দুই দাগের বৃত্ত accepting. প্রতিটি state থেকে 0 আর 1 দুটিরই ঠিক একটি তীর।
এখন যন্ত্রটি একটি string পড়ুক। Sipser-এর বইয়ের ভাষায়: w = w1w2…wn পড়ার run হলো state-এর একটি ক্রম r0, r1, …, rn, যেখানে r0 = q0 আর প্রতিটি i-তে ri+1 = δ(ri, wi+1). M w গ্রহণ করে যদি rn ∈ F. δ total আর deterministic বলে এই ক্রম সবসময় আছে আর একটিই। নিচের stepper 1011 পড়ে।
1q = E (start)2read 1: E → O3read 0: O → O4read 1: O → E5read 1: E → O6O ∉ F → reject
| পড়া অংশ | |
| বাকি অংশ | |
| এ পর্যন্ত 1 | |
| state |
- শুরু। কিছু পড়া হয়নি, r0 = q0 = E. এ পর্যন্ত 1-এর সংখ্যা 0, যা জোড়; state-এর অর্থের সঙ্গে মিলছে।
- প্রথম চিহ্ন 1. δ(E, 1) = O. পড়া অংশ “1”, 1-এর সংখ্যা 1, বিজোড়।
- দ্বিতীয় চিহ্ন 0. δ(O, 0) = O. 0 জোড়-বিজোড় বদলায় না, তাই state একই।
- তৃতীয় চিহ্ন 1. δ(O, 1) = E. “101”-এ দুটি 1, আবার জোড়।
- চতুর্থ চিহ্ন 1. δ(E, 1) = O. “1011”-এ তিনটি 1. ইনপুট শেষ, r4 = O.
- সিদ্ধান্ত। O ∉ F = {E}, তাই 1011 বাতিল। সত্যিই এতে তিনটি, অর্থাৎ বিজোড় সংখ্যক 1. যন্ত্র ৪টি চিহ্নে ঠিক ৪টি transition নিয়েছে।
৩ · State diagram আর transition table — একই যন্ত্রের দুই চেহারা
একটি DFA লেখার তিনটি সমান উপায়: ৫-tuple, state diagram, আর transition table. Diagram মানুষের চোখে দ্রুত ধরা পড়ে; table প্রোগ্রামে সরাসরি বসানো যায়; tuple প্রমাণে কাজে লাগে। Diagram আসলে একটি directed graph (পর্ব ০২): state = node, প্রতিটি δ(p, a) = q একটি তীর p → q, যার গায়ে লেখা a. একই p থেকে q-তে কয়েকটি চিহ্নের তীর থাকলে একটি তীরে “0,1” লিখে দেওয়া হয়।
Table-এর নিয়ম: প্রতিটি সারি একটি state, প্রতিটি কলাম একটি চিহ্ন, ঘরে পরের state. Start state-এর পাশে “→”, accepting state-এর পাশে “∗” দেওয়ার রীতি অনেক বইয়ে আছে। MPAR-এর table মাত্র দুই সারি:
| δ | 0 | 1 |
|---|---|---|
| → ∗ E | E | O |
| O | O | E |
এবার বাজারঘরের অর্ডার-কোড: “BG-” তারপর ঠিক ৪টি অঙ্ক, যেমন BG-0042. দশটি অঙ্কের প্রতিটির জন্য আলাদা তীর আঁকলে ছবি ভরে যায়, তাই এই মডিউলে alphabet-টিকে সংক্ষেপে Σ = {B, G, -, d} লিখি, যেখানে d মানে “0–9-এর যেকোনো একটি অঙ্ক”। (§৭-এর সত্যিকারের run-এ পুরো ১৩টি চিহ্নই ব্যবহার হয়েছে।) Language ORD = {BG-dddd}, এই সংক্ষিপ্ত alphabet-এ একটিমাত্র string.
অর্ডার-কোডের DFA (partial ছবি + dead state)
শুধু “ঠিক পথ”-এর তীর আঁকা। নিয়ম: যে (state, চিহ্ন)-এর তীর আঁকা নেই, সেটি dead state qd-তে যায়।
এমন ছবিকে বলা হয় partial DFA-র ছবি। এটি শুধু লেখার সুবিধা; সংজ্ঞা অনুযায়ী যন্ত্রটি সম্পূর্ণ, কারণ বাদ পড়া প্রতিটি transition qd-তে যায় বলে ঘোষণা করা আছে। নিচের stepper ছবি থেকে সম্পূর্ণ table বানায়, একটি করে সারি।
| δ | B | G | - | d |
|---|---|---|---|---|
| → q0 | q1 | qd | qd | qd |
| q1 | qd | q2 | qd | qd |
| q2 | qd | qd | q3 | qd |
| q3 | qd | qd | qd | q4 |
| q4 | qd | qd | qd | q5 |
| q5 | qd | qd | qd | q6 |
| q6 | qd | qd | qd | q7 |
| ∗ q7 | qd | qd | qd | qd |
| qd | qd | qd | qd | qd |
- কাঠামো। কলাম = Σ-এর চারটি চিহ্ন B, G, -, d. সারি হবে Q-এর প্রতিটি state, ছবির qd-সহ। এখনো কোনো সারি লেখা হয়নি।
- Start state q0. খোলা তীর q0-তে, তাই সারির পাশে “→”। ছবিতে q0 থেকে শুধু B-এর তীর, q1-এ। বাকি তিন ঘর নিয়ম অনুযায়ী qd.
- q1 আর q2. q1 শুধু G চায় (q2-তে), q2 শুধু - চায় (q3-তে)। বাকি সব ঘর qd: যেমন “BB” পড়লে q1-এ B এসেছে, তাই qd.
- চারটি অঙ্কের state. q3, q4, q5, q6 প্রত্যেকে d পেলে এক ঘর এগোয়। অক্ষর বা হাইফেন এলে qd. এই চারটি সারি দেখতে একই রকম, শুধু গন্তব্য আলাদা।
- Accepting state q7. দুই দাগের বৃত্ত, তাই “∗”। q7 থেকে কোনো তীর আঁকা নেই, তাই চারটি ঘরই qd: “BG-00421”-এর পঞ্চম অঙ্ক যন্ত্রকে q7 থেকে qd-তে নিয়ে যায়।
- Dead state qd. ছবির self-loop “B,G,-,d”: চারটি ঘরই qd. একবার ঢুকলে আর বের হওয়া নেই, আর qd ∉ F.
- যাচাই। ৯টি সারি × ৪টি কলাম = ৩৬টি ঘর, প্রতিটিতে ঠিক একটি state. তাই δ: Q × Σ → Q সত্যিই total, আর table-টি একটি বৈধ DFA.
উল্টো দিকে table থেকে ছবি আঁকাও যান্ত্রিক: প্রতিটি সারির প্রতিটি ঘর একটি তীর। একটি ব্যবহারিক পরামর্শ: ছবিতে প্রতিটি state থেকে বের হওয়া তীরগুলোর গায়ে লেখা চিহ্নগুলো গুনুন। DFA-তে প্রতিটি চিহ্ন ঠিক একবার আসতে হবে; কোনো চিহ্ন দুবার এলে যন্ত্রটি deterministic নয়, একবারও না এলে ছবিটি partial.
৪ · Extended transition function δ̂ — পুরো string-এর transition
δ একবারে একটি চিহ্ন নেয়। কিন্তু আমরা জানতে চাই পুরো string পড়ার পর যন্ত্র কোথায়। এর জন্য δ-কে string-এ বাড়িয়ে নিই। সংজ্ঞাটি string-এর গঠন ধরে inductive: প্রতিটি string হয় ε, নয় কোনো ছোট string w-এর পরে একটি চিহ্ন a, অর্থাৎ wa.
DFA M = (Q, Σ, δ, q0, F)-এর জন্য δ̂: Q × Σ∗ → Q এভাবে সংজ্ঞায়িত: সব q ∈ Q, w ∈ Σ∗ আর a ∈ Σ-এর জন্য
δ̂(q, ε) = q এবং δ̂(q, wa) = δ(δ̂(q, w), a)
কথায়: কিছু না পড়লে যন্ত্র যেখানে ছিল সেখানেই থাকে; wa পড়তে হলে আগে w পড়ে যে state-এ পৌঁছায়, সেখান থেকে a-এর একটি transition. Hopcroft–Motwani–Ullman-এর বইয়ে এই চিহ্নটিই δ̂; অনেক বইয়ে একই function লেখা হয় δ∗. এই কোর্সে সবখানে, পর্ব ০৪-সহ, আমরা δ̂ লিখি। একটি চিহ্নের string a-এর জন্য δ̂(q, a) = δ(δ̂(q, ε), a) = δ(q, a), তাই δ̂ সত্যিই δ-এর সম্প্রসারণ। নিচের stepper অর্ডার-কোড DFA-তে δ̂(q0, BGd) সংজ্ঞা ধরে খোলে, তারপর ভেতর থেকে মান বের করে।
1δ̂(q0,BGd) = δ(δ̂(q0,BG), d)2δ̂(q0,BG) = δ(δ̂(q0,B), G)3δ̂(q0,B) = δ(δ̂(q0,ε), B)4δ̂(q0,ε) = q05δ̂(q0,B) = δ(q0,B) = q16δ̂(q0,BG) = δ(q1,G) = q27δ̂(q0,BGd) = δ(q2,d) = qd
| যে string খোলা হচ্ছে | |
| প্রয়োগ হওয়া নিয়ম | |
| জানা মান |
- শেষ চিহ্ন আলাদা। BGd = wa, যেখানে w = BG আর a = d. সংজ্ঞার দ্বিতীয় অংশ: আগে δ̂(q0, BG) জানতে হবে।
- আবার একই নিয়ম। BG = wa, w = B, a = G. এখন দরকার δ̂(q0, B).
- আরেকবার। B = εB, তাই δ̂(q0, B) = δ(δ̂(q0, ε), B). String প্রতিবার এক চিহ্ন ছোট হচ্ছে, তাই এই খোলা একসময় থামবেই।
- ভিত্তি। δ̂(q0, ε) = q0, সংজ্ঞার প্রথম অংশ। এখন আর খোলার কিছু নেই, এবার উল্টো দিকে মান বসানো।
- প্রথম মান। δ̂(q0, B) = δ(q0, B) = q1, table-এর q0 সারি, B কলাম।
- দ্বিতীয় মান। δ̂(q0, BG) = δ(q1, G) = q2. এটি “BG” পড়ার পরের state, যেমন ছবিতে দেখা যায়।
- শেষ মান। δ̂(q0, BGd) = δ(q2, d) = qd, কারণ q2 হাইফেন চায়, অঙ্ক নয়। qd ∉ F = {q7}, তাই “BG7” ধরনের কোড বাতিল।
সংজ্ঞাটি “শেষ চিহ্ন আলাদা” রূপে লেখা, কিন্তু প্রায়ই আমাদের string-কে যেকোনো জায়গায় ভাগ করতে হয়। পরের lemma বলে, x পড়ে তারপর y পড়া আর একসঙ্গে xy পড়া একই কথা। পুরো মডিউলে, বিশেষত পর্ব ০৮-এর product construction আর পর্ব ১৭-এর pumping lemma-তে, এটি বারবার লাগবে।
সব q ∈ Q আর x, y ∈ Σ∗-এর জন্য δ̂(q, xy) = δ̂(δ̂(q, x), y).
প্রমাণ (q আর x স্থির রেখে |y|-এর ওপর induction):
- Base: y = ε. বাম দিক δ̂(q, xε) = δ̂(q, x). ডান দিক δ̂(δ̂(q, x), ε) = δ̂(q, x). সমান। — xε = x আর δ̂-এর প্রথম নিয়ম
- Hypothesis: দৈর্ঘ্য m-এর কোনো y-এর জন্য দাবিটি সত্য। এখন দৈর্ঘ্য m + 1-এর string ya নিই, a ∈ Σ. — induction
- δ̂(q, x(ya)) = δ̂(q, (xy)a) = δ(δ̂(q, xy), a). — concatenation associative; δ̂-এর দ্বিতীয় নিয়ম, w = xy ধরে
- = δ(δ̂(δ̂(q, x), y), a). — hypothesis
- = δ̂(δ̂(q, x), ya). — δ̂-এর দ্বিতীয় নিয়ম, শুরু δ̂(q, x) থেকে, w = y ধরে ∎
লক্ষ করুন, induction হয়েছে y-এর ওপর, x-এর ওপর নয়। কারণ সংজ্ঞা শেষ চিহ্ন আলাদা করে, আর xy-এর শেষ চিহ্ন y-এর শেষ চিহ্ন। ভুল ভেরিয়েবল বাছলে ধাপ ৩ লেখা যায় না। Induction-এর সাধারণ কাঠামো ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১০-এ আছে।
৫ · DFA-র language আর regular language
DFA M w গ্রহণ করে যদি δ̂(q0, w) ∈ F; নইলে M w বাতিল করে। M-এর language
L(M) = {w ∈ Σ∗ : δ̂(q0, w) ∈ F}
M L-কে চেনে (recognizes) যদি L(M) = L. একটি language regular, যদি কোনো DFA তাকে চেনে।
দুটি শব্দের পার্থক্য খেয়াল করুন। “M w গ্রহণ করে” একটি string নিয়ে কথা; “M L চেনে” মানে M ঠিক L-এর string গ্রহণ করে, বেশিও না, কমও না। প্রতিটি DFA ঠিক একটি language চেনে (হয়তো ∅), কিন্তু একটি regular language-এর অসীম সংখ্যক DFA থাকে: যেকোনো DFA-তে একটি অপ্রয়োজনীয় state জুড়ে দিলেই নতুন যন্ত্র, language একই।
এখানে regular language-কে DFA দিয়েই সংজ্ঞায়িত করা হলো। একই শ্রেণিকে regular expression দিয়েও বর্ণনা করা যায়; এই সমতা, Kleene-এর theorem, পর্ব ১৪ আর ১৫-এ দুই দিকে প্রমাণ হবে। তার আগে পর্যন্ত “regular” মানে আমাদের কাছে শুধু “কোনো DFA আছে”। কয়েকটি ছোট উদাহরণ, Σ = {0, 1}:
| Language | সবচেয়ে ছোট একটি DFA |
|---|---|
| ∅ | এক state s, দুই চিহ্নে s-এ ফেরা, F = ∅ |
| Σ∗ | একই এক state, কিন্তু F = {s} |
| {ε} | দুই state: s (শুরু, accepting) আর dead state; s থেকে সব চিহ্নে dead |
| PAR (জোড় সংখ্যক 1) | দুই state E, O (ছবি ৭.১) |
| যেকোনো সসীম language | প্রতিটি prefix-এর জন্য একটি state আর একটি dead state (অনুশীলন ২) |
∅ আর {ε}-এর পার্থক্য এখানে স্পষ্ট দেখা যায়: প্রথমটির যন্ত্র কিছুই নেয় না, দ্বিতীয়টি শুধু ফাঁকা string নেয়, কারণ তার start state accepting. পর্ব ০৩-এর সতর্কবাণী ∅ ≠ {ε} এখানে দুটি ভিন্ন যন্ত্র।
একটি DFA-র সঠিকতার প্রমাণ
“MPAR ঠিক PAR চেনে” একটি দাবি, আর দাবির প্রমাণ লাগে। কৌশলটি পর্ব ০৪-এ “11 নেই”-এর DFA-তে বিস্তারিত দেখানো হয়েছে: প্রতিটি state-এর জন্য একটি বাক্য (invariant), তারপর |w|-এর ওপর induction. এখানে একই ছাঁচ সংক্ষেপে, কারণ এই প্রমাণটি পরীক্ষায় সবচেয়ে বেশি আসে। #1(w) লিখি w-এ 1-এর সংখ্যা।
সব w ∈ {0, 1}∗-এর জন্য: δ̂(E, w) = E ⇔ #1(w) জোড়, আর δ̂(E, w) = O ⇔ #1(w) বিজোড়। ফলে L(MPAR) = PAR.
- Q = {E, O} আর জোড়/বিজোড় দুটি শর্ত পরস্পর বর্জনশীল, তাই দেখানো যথেষ্ট: δ̂(E, w) = P(w), যেখানে P(w) = E যদি #1(w) জোড়, নইলে O. — দুই ⇔ একসঙ্গে
- Base: w = ε. δ̂(E, ε) = E, আর #1(ε) = 0 জোড়, তাই P(ε) = E. — δ̂-এর প্রথম নিয়ম
- Hypothesis: দৈর্ঘ্য n-এর v-এর জন্য δ̂(E, v) = P(v). w = va, a ∈ {0, 1}. — induction
- δ̂(E, va) = δ(δ̂(E, v), a) = δ(P(v), a). — δ̂-এর দ্বিতীয় নিয়ম আর hypothesis
- a = 0: #1(v0) = #1(v), আর δ(E, 0) = E, δ(O, 0) = O, তাই δ(P(v), 0) = P(v) = P(v0). — table
- a = 1: #1(v1) = #1(v) + 1, জোড়-বিজোড় উল্টায়; δ(E, 1) = O আর δ(O, 1) = E-ও উল্টায়, তাই δ(P(v), 1) = P(v1). — table
- F = {E}, তাই w ∈ L(MPAR) ⇔ δ̂(E, w) = E ⇔ P(w) = E ⇔ #1(w) জোড় ⇔ w ∈ PAR. দুই দিকের inclusion একসঙ্গে প্রমাণিত। ∎
প্রমাণ সব দৈর্ঘ্যের নিশ্চয়তা দেয়; গণনা দেয় হিসাবের ভুল ধরার সস্তা উপায়। নিচের ব্লকে পুরো DFA algorithm মাত্র চার লাইনের function accepts. এটি দৈর্ঘ্য 0 থেকে 10-এর সব string-এ MPAR-কে সংজ্ঞার predicate “1-এর সংখ্যা জোড়”-এর সঙ্গে মেলায়, তারপর অর্ডার-কোড DFA-কে Python-এর re module-এর একটি pattern-এর সঙ্গে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।
from itertools import product
import re
def strings(sigma, n): # shortlex: length 0..n
for k in range(n + 1):
for t in product(sigma, repeat=k):
yield "".join(t)
def accepts(M, w): # the whole DFA algorithm
q = M["start"]
for a in w:
q = M["delta"][q, a]
return q in M["F"]
PAR = {"start": "E", "F": {"E"},
"delta": {("E", "0"): "E", ("E", "1"): "O",
("O", "0"): "O", ("O", "1"): "E"}}
n, checked, bad = 10, 0, []
for w in strings("01", n):
checked += 1
if accepts(PAR, w) != (w.count("1") % 2 == 0):
bad.append(w)
print("parity: checked", checked, "strings, mismatches", len(bad))
print("accepted, length <= 3:", [w or "ε" for w in strings("01", 3) if accepts(PAR, w)])
pattern, delta = "BG-dddd", {} # order code over {B, G, -, d}
for i in range(8):
for a in "BG-d":
delta[i, a] = i + 1 if i < 7 and pattern[i] == a else "X"
for a in "BG-d":
delta["X", a] = "X"
ORD = {"start": 0, "F": {7}, "delta": delta}
total = acc = bad = 0
for w in strings("BG-d", 8):
total += 1
acc += accepts(ORD, w)
bad += accepts(ORD, w) != bool(re.fullmatch(r"BG-d{4}", w))
print("order code: strings", total, " accepted", acc, " mismatches", bad)আসল আউটপুট (ব্রাউজারের Python):
parity: checked 2047 strings, mismatches 0
accepted, length <= 3: ['ε', '0', '00', '11', '000', '011', '101', '110']
order code: strings 87381 accepted 1 mismatches 0
দৈর্ঘ্য 0 থেকে 10-এর ২১১ − ১ = ২০৪৭টি string-এর একটিতেও যন্ত্র আর সংজ্ঞা আলাদা উত্তর দেয়নি। দৈর্ঘ্য 3 পর্যন্ত গৃহীত string-গুলো shortlex ক্রমে: ε (শূন্যটি 1, জোড়), তারপর 0, 00, 11 ইত্যাদি। অর্ডার-কোড DFA-তে state 0–7 আর dead state X; দৈর্ঘ্য 8 পর্যন্ত ৮৭৩৮১টি string-এর মধ্যে ঠিক একটি গৃহীত, “BG-dddd”, যা re-এর pattern-এর সঙ্গে প্রতিটি string-এ মিলেছে। মনে রাখুন, এই মিল দৈর্ঘ্য 10 বা 8 পর্যন্ত নিশ্চয়তা দেয়; সব দৈর্ঘ্যের নিশ্চয়তা দেয় উপপাদ্য ৫.২-এর প্রমাণ।
৬ · Dead state, সম্পূর্ণতা আর unreachable state
অর্ডার-কোড DFA-র qd একটি dead state: accepting নয়, আর প্রতিটি চিহ্নে নিজের কাছেই ফেরে। একবার ঢুকলে কোনো ভবিষ্যৎ ইনপুট string-টিকে বাঁচাতে পারে না। বাস্তব ভাষায়, কোড টাইপের সময় “BX” লিখলেই ফর্মটি নিশ্চিত হতে পারে যে এটি আর কখনো বৈধ অর্ডার-কোড হবে না, বাকি অক্ষর যা-ই হোক।
একটি partial transition table δp দেওয়া থাকলে নতুন state qd ∉ Q যোগ করুন; δ(q, a) = δp(q, a) যেখানে সংজ্ঞায়িত, বাকি সব (q, a)-তে আর qd-এর সব চিহ্নে δ(q, a) = qd; F বদলায় না। “যে চিহ্নের তীর নেই, সেখানে যন্ত্র আটকে গিয়ে বাতিল করে”, এই ব্যাখ্যার সঙ্গে নতুন যন্ত্রের language হুবহু এক।
কেন language বদলায় না (প্রমাণের রূপরেখা): যে string-এ partial যন্ত্র কখনো আটকায় না, তাতে দুই যন্ত্র একই পথে চলে আর একই state-এ থামে। যে string-এ কোথাও আটকায়, partial ব্যাখ্যায় সেটি বাতিল; সম্পূর্ণ যন্ত্র সেই মুহূর্তে qd-তে যায়, আর বাকি পুরো ইনপুটে qd-তেই থাকে (|বাকি অংশ|-এর ওপর ছোট একটি induction), qd ∉ F, তাই সেখানেও বাতিল।
তাহলে partial ছবি দিয়েই কাজ চালানো যায় না কেন? কারণ কয়েকটি construction-এ সম্পূর্ণতা অপরিহার্য। সবচেয়ে বিখ্যাত উদাহরণ complement: accepting আর non-accepting state অদলবদল করলে Σ∗ ∖ L(M) পাওয়া যায় শুধু সম্পূর্ণ DFA-তে। Partial যন্ত্রে যে string আটকে যেত, অদলবদলের পরও আটকে যায়, তাই complement-এ যা থাকার কথা তা বাদ পড়ে। এই বাগটি পর্ব ০৮-এ ধাপে ধাপে দেখানো হবে।
আরেক ধরনের অপ্রয়োজনীয় state হলো unreachable state: q0 থেকে কোনো string পড়ে যেখানে পৌঁছানো যায় না, অর্থাৎ কোনো w-এ δ̂(q0, w) = q নয়। এমন state মুছে দিলে language বদলায় না, কারণ কোনো run সেখানে যায়ই না। খোঁজার উপায় graph-এর reachability, BFS দিয়ে। এটি পর্ব ১৯-এর minimization-এর প্রথম ধাপ। Dead state আর unreachable state আলাদা জিনিস: qd পৌঁছানো যায় কিন্তু সেখান থেকে F-এ যাওয়া যায় না; unreachable state-এ পৌঁছানোই যায় না।
নিচের ব্লকে অর্ডার-কোড DFA-র partial table, যাতে একটি পুরোনো নকশার বাড়তি state q8-ও রয়ে গেছে। ব্লকটি table সম্পূর্ণ করে, দুই ব্যাখ্যার language দৈর্ঘ্য 8 পর্যন্ত মেলায়, আর BFS দিয়ে unreachable state খোঁজে।
from collections import deque
from itertools import product
SIGMA = "BG-d"
part = {(0, "B"): 1, (1, "G"): 2, (2, "-"): 3, (3, "d"): 4,
(4, "d"): 5, (5, "d"): 6, (6, "d"): 7,
(8, "d"): 7} # q8: left over from an old design
Q = list(range(9))
def complete(delta, states, sigma, dead="qd"):
full = dict(delta)
for q in states + [dead]:
for a in sigma:
if (q, a) not in full:
full[q, a] = dead
return full
full = complete(part, Q, SIGMA)
print("drawn:", len(part), " added:", len(full) - len(part), " total:", len(full))
def run(delta, w):
q = 0
for a in w:
if (q, a) not in delta:
return False # missing arrow = reject
q = delta[q, a]
return q == 7
same = all(run(part, w) == run(full, w)
for k in range(9) for w in map("".join, product(SIGMA, repeat=k)))
print("same language up to length 8:", same)
seen, todo = {0}, deque([0])
while todo: # BFS from the start state
q = todo.popleft()
for a in SIGMA:
r = full[q, a]
if r not in seen:
seen.add(r)
todo.append(r)
print("reachable:", len(seen), " unreachable:", [q for q in Q if q not in seen])আসল আউটপুট (ব্রাউজারের Python):
drawn: 8 added: 32 total: 40
same language up to length 8: True
reachable: 9 unreachable: [8]
৯টি পুরোনো state আর নতুন qd মিলে ১০টি state, চারটি চিহ্নে মোট ১০ × ৪ = ৪০টি transition; আঁকা ছিল ৮টি, বাকি ৩২টি qd-তে গেছে। দৈর্ঘ্য 8 পর্যন্ত সব string-এ “আটকালে বাতিল” ব্যাখ্যা আর সম্পূর্ণ যন্ত্র একই উত্তর দিয়েছে। BFS start state থেকে ৯টি state-এ পৌঁছেছে (q0–q7 আর qd), কিন্তু q8-এ নয়: কোনো তীর q8-এ ঢোকে না, তাই q8 মুছে দিলে যন্ত্র ছোট হয় আর language একই থাকে।
৭ · DFA একটি প্রোগ্রাম — linear time আর ADFA
প্রোগ্রামারের চোখে DFA খুব পরিচিত একটি জিনিস: একটি variable (বর্তমান state), একটি লুপ (প্রতিটি চিহ্নে একবার), আর লুপের ভেতরে একটি switch, যেখানে প্রতিটি state-এর জন্য একটি case থাকে। কোনো array, list বা recursion নেই। এজন্য DFA-কে প্রায়ই বলা হয় “সবচেয়ে সরল প্রোগ্রাম, যার আচরণ আমরা পুরোপুরি বিশ্লেষণ করতে পারি”। নিচের JavaScript ব্লকে MPAR ঠিক এভাবে লেখা; শেষে একই প্রোগ্রাম বড় ইনপুটে চালিয়ে ধাপ গোনা হয়।
// The parity DFA as a plain program: one variable, one loop, one switch.
// Edit the test strings and press Run again.
function parity(w, trace) {
let q = "E"; // the machine's whole memory
let steps = 0;
for (const a of w) {
if (a !== "0" && a !== "1") return ["not over {0,1}", steps];
switch (q) { // one case per state
case "E": q = (a === "1") ? "O" : "E"; break;
case "O": q = (a === "1") ? "E" : "O"; break;
}
steps++;
if (trace) console.log(` read ${a} -> ${q} left: "${w.slice(steps)}"`);
}
return [q === "E" ? "ACCEPT" : "reject", steps];
}
console.log('"1011", start in E');
console.log(parity("1011", true)[0]);
for (const w of ["", "0110", "10a1"]) {
console.log(JSON.stringify(w).padEnd(7), parity(w, false)[0]);
}
// linear time: exactly one transition per input symbol
for (const n of [10, 1000, 100000]) {
const w = "10".repeat(n / 2);
const [verdict, steps] = parity(w, false);
console.log(`|w| = ${n}: steps = ${steps}, ${verdict}`);
}আসল আউটপুট (ব্রাউজারের JavaScript):
"1011", start in E
read 1 -> O left: "011"
read 0 -> O left: "11"
read 1 -> E left: "1"
read 1 -> O left: ""
reject
"" ACCEPT
"0110" ACCEPT
"10a1" not over {0,1}
|w| = 10: steps = 10, reject
|w| = 1000: steps = 1000, ACCEPT
|w| = 100000: steps = 100000, ACCEPT
প্রথম অংশ §২-এর stepper-এর হুবহু একই run: E → O → O → E → O, বাতিল। ফাঁকা string গৃহীত, কারণ start state E নিজেই accepting. “10a1”-এ a চিহ্নটি Σ-এর বাইরে, তাই প্রোগ্রাম আলাদা করে জানায়; formal DFA-র কাছে এমন ইনপুটের প্রশ্নই ওঠে না, কারণ ইনপুট সবসময় Σ∗-এর। শেষ তিন লাইন: “10” বারবার লিখলে 1-এর সংখ্যা n/2, যা n = 10-এ ৫ (বিজোড়, বাতিল) আর বাকি দুটিতে জোড়। ধাপের সংখ্যা ঠিক |w|, ইনপুট যত বড়ই হোক।
একটি নির্দিষ্ট DFA M-এর জন্য “w ∈ L(M)?” প্রশ্নের উত্তর ঠিক |w|টি transition-এ পাওয়া যায়, প্রতিটি table lookup স্থির সময়ের, আর স্মৃতি লাগে শুধু বর্তমান state-এর জন্য, অর্থাৎ ⌈log2|Q|⌉ বিট, যা |w|-এর ওপর নির্ভর করে না। তাই সময় O(|w|), অতিরিক্ত স্মৃতি O(1).
এর চেয়ে দ্রুত সাধারণভাবে সম্ভব নয়, কারণ বেশিরভাগ language-এ উত্তর দেওয়ার আগে প্রতিটি চিহ্ন অন্তত একবার দেখতেই হয় (PAR-এ শেষ চিহ্নটি না দেখলে জোড়-বিজোড় বলা যায় না)। আরেকটি সুবিধা: DFA ইনপুট জমিয়ে রাখে না, তাই নেটওয়ার্ক থেকে আসা অসীম প্রবাহের ওপরও “এ পর্যন্ত বৈধ কি না” প্রতি মুহূর্তে বলা যায়। Lexer (পর্ব ২২) আর string matching automaton (পর্ব ২৩) ঠিক এই বৈশিষ্ট্য কাজে লাগায়। Big-O notation-এর পুনরালোচনা DSA কোর্সের পর্ব ০৪-এ।
এবার প্রশ্নটি একটু বদলাই। পর্ব ০৫-এ (সমস্যাকে language হিসেবে দেখা) আমরা ঠিক করেছিলাম:
ADFA = {⟨M, w⟩ : M একটি DFA আর M w গ্রহণ করে}
এখানে যন্ত্রটিও ইনপুটের অংশ। একটি algorithm: ⟨M, w⟩ পড়ে, encoding বৈধ না হলে বাতিল; নইলে M-এর table মেনে w-এর ওপর ঠিক |w| ধাপ চালিয়ে শেষ state F-এ কি না দেখে। এই algorithm প্রতিটি ইনপুটে থামে, কারণ ধাপের সংখ্যা |w| দিয়ে সীমিত, আর উত্তর ঠিক, কারণ এটি δ̂-এর সংজ্ঞাই অনুসরণ করে। তাই ADFA decidable; ইনপুটের দৈর্ঘ্যের polynomial সময়েই। Turing machine দিয়ে পূর্ণ প্রমাণ পর্ব ৫০-এ, আর regular language-এর অন্য decision problem (emptiness, equivalence) পর্ব ২০-এ। পার্থক্যটি মনে রাখার মতো: Turing machine-এর জন্য একই প্রশ্ন ATM undecidable (পর্ব ৫১), কারণ সেখানে “কত ধাপ পরে থামবে” আগে থেকে বলা যায় না।
সত্যিকারের run: automata-lib-এ অর্ডার-কোড DFA
নিজের হাতে লেখা simulator-এর পাশাপাশি একটি প্রতিষ্ঠিত library-তে একই যন্ত্র বানিয়ে দেখা ভালো অভ্যাস। Python package automata-lib (MIT লাইসেন্স) DFA, NFA, PDA আর Turing machine-এর জন্য বানানো। এখানে পুরো ১৩ চিহ্নের alphabet {B, G, -, 0, …, 9} ব্যবহার করা হয়েছে, d-এর সংক্ষেপ ছাড়াই। এটি সত্যিকারের run: automata-lib 9.2.0, Python 3.12, একটি uv venv-এ।
~/bazarghar-toc$ cat order_code.py
from automata.fa.dfa import DFA
DIG = "0123456789"
SIGMA = set("BG-") | set(DIG)
need = ["B", "G", "-"] + [DIG] * 4 # what position i expects
delta = {}
for i in range(8):
q = f"q{i}"
delta[q] = {}
for a in SIGMA:
ok = i < 7 and a in need[i]
delta[q][a] = f"q{i+1}" if ok else "qd"
delta["qd"] = {a: "qd" for a in SIGMA}
M = DFA(states=set(delta), input_symbols=SIGMA, transitions=delta,
initial_state="q0", final_states={"q7"})
… (তারপর কয়েকটি string-এ accepts_input, read_input_stepwise,
cardinality, isempty, isfinite আর minify ডাকা হয়েছে)
~/bazarghar-toc$ uv run python order_code.py
states: 9 symbols: 13
'BG-0042' True
'BG-42' False
'bg-0042' not over Sigma
'BG-00421' False
'' False
path BG-07: ['q0', 'q1', 'q2', 'q3', 'q4', 'q5']
accepted strings: 10000
empty language? False finite? True
states after minify: 9 same language: True
৯টি state আর ১৩টি চিহ্ন, অর্থাৎ ১১৭টি transition. “BG-0042” গৃহীত; “BG-42”-এ অঙ্ক কম, “BG-00421”-এ বেশি, ফাঁকা string-এ কিছুই নেই, তিনটিই বাতিল। ছোট হাতের “bg” Σ-এর বাইরে, তাই স্ক্রিপ্ট সেটিকে যন্ত্রে দেয়ইনি। “BG-07” পড়ার পথ q0 থেকে q5 পর্যন্ত, পাঁচটি চিহ্নে পাঁচটি transition. Library গুনে বলেছে language-এ ঠিক ১০০০০টি string, যা ১০৪, চারটি অঙ্কের সব সম্ভাবনা। Minify-এর পরও ৯টি state, অর্থাৎ এই যন্ত্রে কোনো বাড়তি state নেই (কেন, তা পর্ব ১৮–১৯-এ)। এরপর একই library-তে একটি transition বাদ দিয়ে partial যন্ত্র বানানোর চেষ্টা:
~/bazarghar-toc$ cat partial.py
from automata.fa.dfa import DFA
try:
DFA(states={"E", "O"}, input_symbols={"0", "1"},
transitions={"E": {"0": "E", "1": "O"}, "O": {"1": "E"}},
initial_state="E", final_states={"E"})
except Exception as e:
print(type(e).__name__ + ":", e)
~/bazarghar-toc$ uv run python partial.py
MissingSymbolError: state O is missing transitions for symbol "0"
Library সংজ্ঞাটি কড়াভাবে মানে: δ total না হলে DFA বানাতেই দেয় না। (এর একটি allow_partial বিকল্প আছে, যা §৬-এর “আটকালে বাতিল” ব্যাখ্যা ব্যবহার করে।) নিজের প্রোগ্রামেও এমন একটি পরীক্ষা রাখা ভালো: table-এ ঠিক |Q| · |Σ|টি ঘর আছে কি না।
৮ · DFA গোনা — কতগুলো যন্ত্র, কতগুলো language
Q = {q0, …, qn−1} আর |Σ| = k স্থির রেখে কতগুলো ভিন্ন DFA লেখা যায়? প্রতিটি অংশ আলাদাভাবে বাছাই করা যায়, তাই গুণের নিয়ম (ডিসক্রিট ম্যাথমেটিক্সের গণনার মূলনীতি) খাটে:
- δ: nkটি ঘরের প্রতিটিতে nটি state-এর যেকোনোটি, তাই nnk উপায়।
- F: Q-এর যেকোনো subset, তাই 2n উপায়।
- Start state: q0 স্থির রাখলে ১ উপায়; যেকোনো state হতে দিলে n উপায়।
Start state q0 স্থির রেখে n state আর k চিহ্নের DFA-র সংখ্যা nnk · 2n. Start state-ও বাছাই করতে দিলে n · nnk · 2n = nnk+1 · 2n.
সংখ্যাগুলো দ্রুত বাড়ে: n = 2, k = 2-এ 24 · 22 = 64; n = 3-এ 36 · 8 = 5832. কিন্তু ভিন্ন যন্ত্র মানেই ভিন্ন language নয়। কতগুলো ভিন্ন language আসে, তা বের করতে প্রতিটি যন্ত্রের আচরণ তুলনা করতে হয়। এখানে একটি জানা তথ্য কাজে লাগে (প্রমাণ পর্ব ১৮–২০-এর ধারণায়): n1 আর n2 state-এর দুটি DFA-র language আলাদা হলে, দৈর্ঘ্য বড়জোর n1 + n2 − 2-এর একটি string তাদের আলাদা করে। তাই দৈর্ঘ্য 2n − 1 পর্যন্ত সব string-এ আচরণ মিললে দুটি n-state যন্ত্রের language নিশ্চিতভাবে এক। নিচের ব্লক সূত্রটি পূর্ণ গণনায় মেলায়, তারপর language গোনে।
from itertools import product
def all_dfas(n, sigma): # states 0..n-1, start state 0
keys = [(q, a) for q in range(n) for a in sigma]
for targets in product(range(n), repeat=len(keys)):
delta = dict(zip(keys, targets))
for bits in product([0, 1], repeat=n):
yield delta, {q for q in range(n) if bits[q]}
for n, k in [(1, 1), (1, 2), (2, 1), (2, 2), (3, 2)]:
sigma = "01"[:k]
count = sum(1 for _ in all_dfas(n, sigma))
print(f"n={n} k={k}: enumerated {count:5}, formula n^(nk)*2^n = {n**(n*k) * 2**n}")
def sig(delta, F, sigma, L): # behaviour on all strings up to length L
out = []
for m in range(L + 1):
for w in product(sigma, repeat=m):
q = 0
for a in w:
q = delta[q, a]
out.append(q in F)
return tuple(out)
for n in (1, 2, 3):
langs = {sig(d, F, "01", 2 * n - 1) for d, F in all_dfas(n, "01")}
total = n**(2 * n) * 2**n
print(f"{n}-state DFAs over {{0,1}}: {total} machines, {len(langs)} languages")আসল আউটপুট (ব্রাউজারের Python):
n=1 k=1: enumerated 2, formula n^(nk)*2^n = 2
n=1 k=2: enumerated 2, formula n^(nk)*2^n = 2
n=2 k=1: enumerated 16, formula n^(nk)*2^n = 16
n=2 k=2: enumerated 64, formula n^(nk)*2^n = 64
n=3 k=2: enumerated 5832, formula n^(nk)*2^n = 5832
1-state DFAs over {0,1}: 2 machines, 2 languages
2-state DFAs over {0,1}: 64 machines, 26 languages
3-state DFAs over {0,1}: 5832 machines, 1054 languages
পাঁচটি ক্ষেত্রেই একটি একটি করে গোনা সংখ্যা সূত্রের সঙ্গে মিলেছে। এক state-এর দুটি যন্ত্র ঠিক দুটি language দেয়: ∅ আর Σ∗. দুই state-এর ৬৪টি যন্ত্র মাত্র ২৬টি ভিন্ন language দেয়, আর তিন state-এর ৫৮৩২টি যন্ত্র ১০৫৪টি। অর্থাৎ বেশিরভাগ যন্ত্র অন্য কোনো যন্ত্রের “পুনরাবৃত্তি”: state-এর নাম অদলবদল, unreachable state, বা একই কাজ করা দুটি state. Start state-ও বাছাই করতে দিলে যন্ত্রের সংখ্যা n গুণ হয়, কিন্তু নতুন কোনো language আসে না, কারণ state-গুলোর নাম বদলে যেকোনো start state-কে q0 বানানো যায়। এখানে n state-এর যন্ত্রের language-এর মধ্যে কম state-এর language-ও আছে (বাড়তি state জুড়ে দেওয়া যায়), তাই ২৬ মানে “বড়জোর ২টি state লাগে এমন language”-এর সংখ্যা।
এই গণনার একটি গভীর ফল: প্রতিটি n-এর জন্য বড়জোর n state-এর DFA সসীম সংখ্যক, তাই তারা সসীম সংখ্যক language চেনে। সব n মিলিয়ে DFA-র সেট countable, অথচ পর্ব ০২-এ দেখেছেন Σ∗-এর সব subset-এর সেট uncountable. তাই “বেশিরভাগ language regular নয়”, যদিও কোনো নির্দিষ্ট language-কে non-regular প্রমাণ করতে পর্ব ১৭–১৮-এর হাতিয়ার লাগে।
সাধারণ ভুল
| ভুল | কেন ভুল, কী করবেন |
|---|---|
| কোনো state থেকে একটি চিহ্নের তীর নেই, আর কোনো ঘোষণাও নেই | δ total নয়; dead state যোগ করুন বা “বাকি সব qd-তে” লিখুন |
| একই state থেকে একই চিহ্নের দুটি তীর | এটি NFA, DFA নয় (পর্ব ০৯) |
| ε-এর কথা ভুলে যাওয়া | Language-এ ε থাকলে q0 ∈ F, না থাকলে q0 ∉ F; আলাদা করে মেলান |
| “ঠিক ৪টি অঙ্ক” চেয়ে ৪-এর পরে আরও অঙ্ক নেওয়া | Accepting state থেকেও বের হওয়ার তীর লাগে, এখানে qd-তে |
| দুই state-এর অর্থ এক, অথচ আলাদা রাখা | ভুল নয়, কিন্তু অপ্রয়োজনীয়; minimization পর্ব ১৯-এ |
| “দৈর্ঘ্য 10 পর্যন্ত মিলেছে, তাই ঠিক” | গণনা প্রমাণ নয়; প্রতিটি state-এর invariant লিখে induction দিন |
আরও গভীরে: n state-এর DFA কতগুলো ভিন্ন language চেনে, তার সঠিক সূত্র জানা নেই; গবেষকেরা ছোট n-এর জন্য কম্পিউটারে গুনেছেন আর ওপর-নিচের সীমা প্রমাণ করেছেন (যেমন Domaratzki, Kisman আর Shallit-এর ২০০২ সালের “On the Number of Distinct Languages Accepted by Finite Automata with n States” নামের প্রবন্ধটি)। §৮-এর ২, ২৬, ১০৫৪ আমাদের নিজের পূর্ণ গণনার ফল। আরেকটি বিখ্যাত খোলা প্রশ্ন Černý-এর অনুমান (১৯৬০-এর দশক): একটি DFA-র যদি এমন কোনো “synchronizing” string থাকে, যা যেকোনো state থেকে একই state-এ নিয়ে যায়, তবে দৈর্ঘ্য (n − 1)2-এর মধ্যেই একটি থাকবে কি না, তা আজও প্রমাণিত নয়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এমন প্রশ্ন প্রায়ই আসে:
- DFA-র formal definition দিন। M = (Q, Σ, δ, q0, F), δ: Q × Σ → Q total, q0 ∈ Q, F ⊆ Q.
- δ̂ কী, কীভাবে সংজ্ঞায়িত? δ̂(q, ε) = q, δ̂(q, wa) = δ(δ̂(q, w), a); পুরো string পড়ার পরের state.
- একটি DFA ε গ্রহণ করে কখন? ঠিক যখন q0 ∈ F.
- n state আর k চিহ্নের DFA কয়টি (start স্থির)? nnk · 2n.
- DFA-তে membership-এর time complexity? O(|w|), অতিরিক্ত স্মৃতি O(1); তাই ADFA decidable.
৯ · AI-এর যুগে — AI-এর আঁকা DFA কীভাবে যাচাই করবেন
“অমুক language-এর DFA দাও” চাইলে AI সহকারী সাধারণত দ্রুত একটি table বা ছবি দেয়, আর সেটি দেখতে বিশ্বাসযোগ্য। কিন্তু DFA-তে একটি ঘরের ভুলই পুরো language বদলে দেয়। এই বিষয়ে কয়েকটি ভুল বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| কিছু transition বাদ (dead state নেই), অথচ “complete DFA” বলা | ঘর গুনুন: ঠিক |Q| · |Σ|টি হতে হবে; §৬-এর complete ফাংশন চালান |
| গোনায় এক কম-বেশি (“অন্তত ৩টি” চেয়ে “ঠিক ৩টি”) | দৈর্ঘ্য 0 থেকে 10-এর সব string-এ সংজ্ঞার predicate-এর সঙ্গে মেলান, §৫-এর ব্লকের মতো |
| ε ভুল: start state-কে ভুলভাবে accepting করা বা না করা | সবার আগে ফাঁকা string-টি আলাদা করে পরীক্ষা করুন |
| সঠিকতার “প্রমাণ” শুধু কয়েকটি উদাহরণ, বা এক দিক | প্রতিটি state-এর invariant আর |w|-এর ওপর induction চান; ⊆ আর ⊇ দুটিই |
| Theorem-এর শর্ত বাদ, যেমন “state অদলবদল করলেই complement” | শর্ত খুঁজুন: complement-এর জন্য DFA সম্পূর্ণ হতে হবে |
| বানানো ইতিহাস বা reference | Sipser বা Hopcroft–Motwani–Ullman-এর মতো বিশ্বস্ত বইয়ে মেলান |
AI-এর কাছে DFA চাইলে এমনভাবে চান, যাতে উত্তর নিজেই যাচাইযোগ্য হয়:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
একটি ভালো অভ্যাস: AI-এর table পড়ার আগে §৫-এর accepts ফাংশনে বসিয়ে predicate-এর সঙ্গে মেলান। পাল্টা-উদাহরণ পেলে সেটিই AI-কে ফেরত দিন (“এই DFA '0' গ্রহণ করে, অথচ করার কথা নয়”); একটি নির্দিষ্ট string দেখালে AI সাধারণত দ্রুত ভুলটি ঠিক করে। পাল্টা-উদাহরণ না পেলেও invariant আর প্রমাণ পড়ুন, কারণ গণনা শুধু সসীম অংশের নিশ্চয়তা দেয়।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১বাস্তব কম্পিউটারের স্মৃতিও সসীম। তাহলে কম্পিউটার কি আসলে একটি বিশাল DFA? তবু আমরা Turing machine দিয়ে ভাবি কেন?
কঠোর অর্থে হ্যাঁ। একটি কম্পিউটারের RAM, register আর disk মিলিয়ে যদি b বিট থাকে, তবে তার সম্ভাব্য অবস্থা বড়জোর 2bটি, আর প্রতিটি ইনপুট-ঘটনায় সে একটি অবস্থা থেকে নির্দিষ্ট আরেকটিতে যায়। এটি একটি DFA-র সংজ্ঞাই মানে। সমস্যা হলো সংখ্যাটির আকার: মাত্র এক কিলোবাইট স্মৃতিতেই 28192টি অবস্থা, যা পর্যবেক্ষণযোগ্য মহাবিশ্বের আনুমানিক কণার সংখ্যার চেয়ে বহুগুণ বেশি বলে সাধারণত বলা হয়। এমন যন্ত্রের state diagram আঁকা বা বিশ্লেষণ করা অর্থহীন।
আরও গুরুত্বপূর্ণ কথা: DFA মডেল ইনপুটের আকারের সঙ্গে স্মৃতি বাড়তে দেয় না। একটি প্রোগ্রাম যখন বড় ফাইল পেলে বড় array বানায়, তখন আমরা তাকে “এই প্রোগ্রাম যেকোনো দৈর্ঘ্যের ইনপুট সামলায়” হিসেবে ভাবি, আর প্রয়োজনে আরও স্মৃতি জোগাড় করা যায়, এমন ধরে নিই। এই আদর্শীকরণই Turing machine-এর অসীম tape (পর্ব ৪৩)। সুষম বন্ধনী পরীক্ষার মতো একটি কাজ যেকোনো সসীম যন্ত্র একটি নির্দিষ্ট গভীরতা পর্যন্তই পারে, কিন্তু একটি সরল counter-ওয়ালা প্রোগ্রাম “সব গভীরতায়” পারে, এই পার্থক্যটি আমরা ধরতে চাই। তাই প্রশ্নটি “এই যন্ত্রে কতটুকু স্মৃতি” নয়, বরং “ইনপুট বাড়লে স্মৃতি কীভাবে বাড়ে”।
অন্যদিকে, যেখানে স্মৃতি সত্যিই ছোট আর স্থির, সেখানে DFA মডেল খুব কাজের। একটি network protocol-এর connection-এর অবস্থা, একটি লিফট controller, একটি UI-এর বোতামের অবস্থা, বা একটি hardware circuit: এদের কয়েক ডজন state, আর এখানে DFA বা তার আত্মীয় মডেল (পর্ব ১২-এর Mealy ও Moore, পর্ব ২৪-এর software state machine) দিয়ে প্রতিটি সম্ভাব্য অবস্থা পরীক্ষা করা যায়। পর্ব ৭৭-এর model checking ঠিক এভাবে বড় কিন্তু সসীম state space ঘুরে দেখে।
মূল উপলব্ধি: প্রতিটি বাস্তব কম্পিউটার আক্ষরিক অর্থে সসীম-state যন্ত্র, কিন্তু মডেল বাছাই হয় প্রশ্ন অনুযায়ী: ইনপুটের সঙ্গে স্মৃতি বাড়ার আচরণ ধরতে Turing machine, আর ছোট, স্থির স্মৃতির নিয়ন্ত্রণ-ব্যবস্থা বিশ্লেষণে DFA.
প্র ০২Neuron-এর মডেল থেকে DFA-র formal definition: ১৯৪৩ থেকে ১৯৫৯ সালের মধ্যে ধারণাটি কীভাবে তৈরি হলো?
Finite automaton-এর ইতিহাস শুরু হয় কম্পিউটার বিজ্ঞানের বাইরে। ১৯৪৩ সালে স্নায়ুবিজ্ঞানী Warren McCulloch আর যুক্তিবিদ Walter Pitts একটি প্রবন্ধে neuron-কে খুব সরল যুক্তির একক হিসেবে মডেল করেন: প্রতিটি neuron হয় সক্রিয়, নয় নিষ্ক্রিয়, আর পরের মুহূর্তের অবস্থা নির্ভর করে বর্তমান ইনপুটের ওপর। এমন সসীম সংখ্যক neuron-এর জাল আসলে একটি সসীম-state যন্ত্র।
Stephen Kleene এই জাল কোন ধরনের “ঘটনার ক্রম” চিনতে পারে, সেই প্রশ্ন তোলেন। তাঁর কাজ ১৯৫১ সালের দিকে একটি RAND প্রতিবেদনে আসে আর ১৯৫৬ সালে “Automata Studies” সংকলনে প্রকাশিত হয় বলে জানা যায়। সেখানেই তিনি “regular event” নামটি দেন আর দেখান যে এই জালগুলো ঠিক সেই ক্রমগুলো চেনে, যা আজ আমরা regular expression দিয়ে লিখি। এ জন্যই language-এর নাম “regular”, আর এই সমতাকে বলা হয় Kleene-এর theorem (পর্ব ১৪–১৫)।
একই সময়ে প্রকৌশলের দিক থেকে switching circuit নিয়ে কাজ হচ্ছিল। David Huffman (১৯৫৪), George Mealy (১৯৫৫) আর Edward Moore (১৯৫৬) sequential circuit আর “sequential machine”-এর মডেল দেন, যেখানে যন্ত্র output-ও দেয়; এ থেকেই পর্ব ১২-এর Mealy আর Moore machine. আজ আমরা যে পরিষ্কার ৫-tuple সংজ্ঞা ব্যবহার করি, তা মূলত Michael Rabin আর Dana Scott-এর ১৯৫৯ সালের প্রবন্ধ “Finite Automata and Their Decision Problems”-এর ধাঁচের। সেখানে তাঁরা neuron বা circuit-এর বিবরণ বাদ দিয়ে যন্ত্রটিকে বিমূর্ত গাণিতিক বস্তু হিসেবে লেখেন, nondeterministic automaton সংজ্ঞায়িত করেন, আর দেখান যে এটি deterministic-এর চেয়ে বেশি শক্তিশালী নয় (পর্ব ১০)। এই কাজের জন্য তাঁরা ১৯৭৬ সালে Turing Award পান।
এই ইতিহাস থেকে একটি শিক্ষা: একটি ভালো সংজ্ঞা অপ্রয়োজনীয় বিবরণ ছেঁটে ফেলে। Neuron-এর রসায়ন, circuit-এর voltage বা লিফটের মোটর, সব বাদ দিলে থাকে শুধু state, চিহ্ন আর নিয়ম, আর তখনই একই উপপাদ্য সব ক্ষেত্রে খাটে।
মূল উপলব্ধি: Finite automaton-এর ধারণা neuron-এর মডেল, switching circuit আর যুক্তিবিদ্যা থেকে প্রায় একসঙ্গে এসেছে; Rabin–Scott-এর বিমূর্ত সংজ্ঞা এই ধারাগুলোকে এক গাণিতিক কাঠামোয় বেঁধেছে।
প্র ০৩δ-কে total রাখার নিয়ম কি শুধু বইয়ের আনুষ্ঠানিকতা, নাকি বাস্তব software-এও এর দাম আছে?
প্রচলিত বইগুলো এখানে পুরোপুরি একমত নয়। Sipser আর Hopcroft–Motwani–Ullman দুজনেই DFA-র δ-কে total function ধরেন; তবু অনেক বই আর লেকচার-নোট ছবিতে dead state বাদ দেওয়ার রীতি মেনে নেয়, যদি সেটি স্পষ্ট বলা থাকে। কিছু বই আর library “partial DFA” আলাদা মডেল হিসেবে রাখে, যেখানে না-থাকা transition মানে বাতিল। §৬-এ দেখেছেন, language-এর দিক থেকে দুই ব্যাখ্যা সমান, তাই এটি “শুধু রীতি” মনে হতে পারে।
কিন্তু পার্থক্যটি ধরা পড়ে construction-এ। Complement-এ state অদলবদল শুধু সম্পূর্ণ DFA-তে কাজ করে। পর্ব ০৮-এর product construction-এ দুটি যন্ত্র একসঙ্গে চালাতে হয়; একটি আটকে গেলে অন্যটির কী হবে, তা partial মডেলে আলাদা নিয়ম চায়। আর সংজ্ঞা যত সরল, প্রমাণ তত পরিষ্কার: total δ থাকলে δ̂ সবসময় সংজ্ঞায়িত, প্রতিটি lemma-তে “যদি সংজ্ঞায়িত থাকে” লিখতে হয় না।
বাস্তব software-এ একই প্রশ্ন আসে switch statement-এর default case হিসেবে। একটি checkout workflow ভাবুন: অবস্থা “কার্টে”, “ঠিকানা দেওয়া”, “পেমেন্ট বাকি”, “সম্পন্ন”। কোনো অবস্থায় অপ্রত্যাশিত ঘটনা এলে, যেমন “সম্পন্ন” অবস্থায় আবার “পেমেন্ট” বার্তা, প্রোগ্রাম কী করবে? যদি এটি আগে থেকে ঠিক করা না থাকে, তবে আচরণ নির্ভর করে কোড কে লিখেছেন তার ওপর, আর এখানেই বাগ ও নিরাপত্তার ফাঁক জন্মায়। অনেক network protocol-এর নির্দেশিকায় প্রতিটি অবস্থায় অপ্রত্যাশিত বার্তার আচরণ আলাদা করে লেখা থাকে, যা কার্যত δ-কে total করা। Software testing-এ state-transition testing ঠিক এই “অবৈধ transition”-গুলো খোঁজে (সফটওয়্যার টেস্টিং কোর্সের পর্ব ১০)।
তাই নিয়মটির ব্যবহারিক অনুবাদ: প্রতিটি অবস্থায় প্রতিটি সম্ভাব্য ঘটনার একটি ঘোষিত ফল থাকবে, আর “ভুল পথ”-এর জন্য একটি স্পষ্ট error state থাকবে, যেখান থেকে চুপচাপ স্বাভাবিক অবস্থায় ফিরে আসা যায় না।
মূল উপলব্ধি: Total δ language-এর দিক থেকে কিছু যোগ করে না, কিন্তু construction আর প্রমাণ সরল করে; software-এ এর সমতুল্য হলো প্রতিটি অবস্থায় প্রতিটি ঘটনার ঘোষিত আচরণ আর একটি স্পষ্ট error state.
প্র ০৪DFA-তে membership linear time-এ হয়। তাহলে বাস্তবের সব pattern matching কেন সরাসরি DFA বানিয়ে করা হয় না?
Linear time শুনতে চমৎকার, কিন্তু তার একটি লুকানো শর্ত আছে: DFA-টি আগে থেকে হাতে থাকতে হবে। বাস্তবে আমরা সাধারণত একটি regular expression বা কয়েকটি pattern দিয়ে শুরু করি। সেখান থেকে প্রথমে একটি NFA পাওয়া সহজ (পর্ব ১৪), আর NFA থেকে DFA-তে যেতে subset construction লাগে (পর্ব ১০)। সমস্যা হলো, কিছু pattern-এর জন্য DFA-র state-এর সংখ্যা NFA-র তুলনায় exponential হয়ে যায়: “শেষ থেকে n-তম চিহ্ন 1” language-এর NFA-তে n + 1টি state, অথচ যেকোনো DFA-তে অন্তত 2nটি লাগে, যা পর্ব ১০-এ প্রমাণ হবে।
তাই প্রকৌশলীরা একটি আপসের পথ নেন। Ken Thompson ১৯৬০-এর দশকের শেষ দিকে একটি text editor-এর জন্য regex থেকে NFA বানিয়ে সেটি সরাসরি simulate করার পদ্ধতি দেন বলে জানা যায়: একসঙ্গে সব সম্ভাব্য state-এর সেট ধরে রাখা, যাতে সময় |w| আর NFA-র আকারের গুণফলের মতো থাকে। আরেক কৌশল “lazy DFA”: শুধু ইনপুটে সত্যিই যে state-গুলো আসে, সেগুলো চলার পথে বানিয়ে cache-এ রাখা। ১৯৭০-এর দশকে Unix-এর lex-এর মতো lexer generator অন্যদিকে পুরো DFA আগেই বানিয়ে ফেলে, কারণ programming language-এর token pattern সাধারণত ছোট, আর একবার বানানো DFA লাখো বার চলে (পর্ব ২২)।
তৃতীয় একটি কারণ: অনেক জনপ্রিয় regex engine backtracking দিয়ে চলে, যা DFA নয়। এরা backreference-এর মতো সুবিধা দেয়, যা regular language-এর বাইরে, কিন্তু কিছু pattern-এ সময় exponential হয়ে যেতে পারে। এর নিরাপত্তা-দিক ReDoS, যা পর্ব ২১-এ নিজের যন্ত্রে নিরাপদভাবে মেপে দেখবেন।
অর্থাৎ বাছাইটি তিনটি খরচের মধ্যে: DFA বানানোর সময় আর স্মৃতি, প্রতিটি ইনপুট পড়ার সময়, আর কোন বৈশিষ্ট্য (যেমন backreference) চাই।
মূল উপলব্ধি: DFA-র linear-time membership সত্য, কিন্তু DFA বানানোর খরচ কখনো exponential; তাই বাস্তব ব্যবস্থা পুরো DFA, NFA simulation, lazy DFA আর backtracking-এর মধ্যে কাজ অনুযায়ী বাছাই করে।
প্র ০৫দুই state-এর ৬৪টি যন্ত্র অথচ মাত্র ২৬টি language: DFA গোনা থেকে আমরা কী শিখি?
প্রথম শিক্ষা: যন্ত্র আর language এক জিনিস নয়। একই language-এর অনেক DFA, আর এদের বেশিরভাগ একে অপরের সামান্য রূপান্তর: state-এর নাম অদলবদল, একটি unreachable state, বা একই আচরণের দুটি state. এখানে একটি স্বাভাবিক প্রশ্ন আসে: একটি language-এর “সেরা” DFA কি আছে? উত্তর হ্যাঁ, আর এটি এই কোর্সের সবচেয়ে সুন্দর ফলগুলোর একটি। Myhill–Nerode theorem (পর্ব ১৮) বলে, প্রতিটি regular language-এর একটি সবচেয়ে কম state-এর DFA আছে, আর state-এর নাম বাদ দিলে সেটি অনন্য। পর্ব ১৯-এর minimization algorithm যেকোনো DFA থেকে সেটি বের করে। ফলে “দুটি DFA কি একই language চেনে?” প্রশ্নটি দুটি minimal DFA মেলানোর প্রশ্নে নেমে আসে, যা decidable (পর্ব ২০)।
দ্বিতীয় শিক্ষা: গণনা দিয়ে অস্তিত্বের প্রমাণ। n state-এর DFA বড়জোর nnk · 2nটি, তাই তারা বড়জোর ততগুলো language চেনে। যদি কোনো language-পরিবারে এর চেয়ে বেশি সদস্য থাকে, তবে তাদের কোনোটির জন্য n-এর বেশি state লাগবেই, কোনটির জন্য তা না জেনেও। Claude Shannon ১৯৪৯ সালে Boolean function-এর জন্য ঠিক এমন যুক্তি দিয়ে দেখান যে বেশিরভাগ function-এর জন্য বিশাল circuit লাগে, যদিও কোনো নির্দিষ্ট function-এর জন্য তা প্রমাণ করা আজও কঠিন (পর্ব ৭০)।
তৃতীয় শিক্ষা: সংখ্যার পরিমাপ। ১০৫৪ সংখ্যাটি এসেছে ৫৮৩২টি যন্ত্র থেকে, আর state বাড়লে দুই সংখ্যার ফারাক আরও বাড়ে বলে ছোট n-এর গণনা ইঙ্গিত দেয়। কিন্তু ঠিক কতগুলো ভিন্ন language, তার সাধারণ সূত্র জানা নেই; “আরও গভীরে” বাক্সে যেমন বলা হয়েছে, এটি এখনো গবেষণার বিষয়। এমন একটি সরল মডেলেও খোলা প্রশ্ন থাকা আমাদের মনে করিয়ে দেয় যে গণনার তত্ত্ব একটি জীবন্ত বিষয়।
মূল উপলব্ধি: DFA গোনা দেখায় যে একই language-এর বহু যন্ত্র আছে, যার মধ্যে একটি অনন্য সবচেয়ে ছোট যন্ত্র (Myhill–Nerode), আর সসীম সংখ্যক যন্ত্রের যুক্তি দিয়েই প্রমাণ করা যায় যে কিছু language-এর জন্য বেশি state লাগবে।
অনুশীলন
আগে খাতায় করুন, তারপর উত্তর খুলে মেলান।
-
নকশা: Σ = {a, b}-এর ওপর L = {w : w a দিয়ে শুরু আর b দিয়ে শেষ}-এর একটি সম্পূর্ণ DFA নকশা করুন। ৫-tuple, transition table আর প্রতিটি state-এর অর্থ লিখুন। ε আর “ab” গৃহীত হয় কি না, বলুন।
Q = {s, A, B, D}, q0 = s, F = {B}.
δ a b অর্থ → s A D কিছু পড়া হয়নি A A B a-তে শুরু, a-তে শেষ ∗ B A B a-তে শুরু, b-তে শেষ D D D b-তে শুরু: dead state - ε: s ∉ F, তাই বাতিল; সঠিক, কারণ ε a দিয়ে শুরু হয় না।
- “ab”: s → A → B, গৃহীত। “ba”: s → D, বাতিল, বাকি যা-ই আসুক।
- সঠিকতা: “অর্থ” কলামটিই invariant; |w|-এর ওপর induction-এ প্রতিটি সারির দুই ঘর মেলানো যায়। দৈর্ঘ্য 12 পর্যন্ত সব string-এ scratch-এ পূর্ণ গণনায় মেলানো।
-
প্রমাণ: প্রমাণ করুন, যেকোনো সসীম language L ⊆ Σ∗ regular. ইঙ্গিত: L-এর string-গুলোর প্রতিটি prefix-এর জন্য একটি state, আর একটি dead state.
Construction: P = {u : u কোনো x ∈ L-এর prefix}, যা সসীম, কারণ প্রতিটি x-এর |x| + 1টি prefix থাকে। Q = P ∪ {qd}, q0 = ε, F = L. δ(u, a) = ua যদি ua ∈ P, নইলে qd; আর δ(qd, a) = qd.
- Claim: সব w-এর জন্য δ̂(ε, w) = w যদি w ∈ P, নইলে qd. |w|-এর ওপর induction. — invariant
- Base: δ̂(ε, ε) = ε, আর ε ∈ P (L ≠ ∅ হলে; L = ∅ হলে এক state-এর F = ∅ যন্ত্রই যথেষ্ট)।
- Step, w = va: v ∈ P হলে δ̂(ε, va) = δ(v, a), যা va যদি va ∈ P, নইলে qd. v ∉ P হলে va-ও P-তে নেই (prefix-এর prefix prefix), আর δ(qd, a) = qd. — δ̂-এর সংজ্ঞা
- তাই δ̂(ε, w) ∈ F ⇔ w ∈ P আর w ∈ L ⇔ w ∈ L. M সম্পূর্ণ আর সসীম, তাই L regular. ∎
উদাহরণ L = {BG, BGD, G}: P = {ε, B, BG, BGD, G}, মোট ৬টি state; দৈর্ঘ্য 6 পর্যন্ত সব string-এ scratch-এ মেলানো।
-
আউটপুট অনুমান: কোড না চালিয়ে বলুন কী ছাপা হবে, আর যন্ত্রটি কোন language চেনে। তারপর যেকোনো Python-এ চালিয়ে মেলান।
d = {("p","a"):"q", ("p","b"):"p", ("q","a"):"q", ("q","b"):"r", ("r","a"):"r", ("r","b"):"r"} def run(w): q = "p" for a in w: q = d[q, a] return q for w in ["bba", "abba", "baab", ""]: print(repr(w), run(w), run(w) == "r")'bba' q False 'abba' r True 'baab' r True '' p Falsebba: p → p → p → q; শেষ a পড়ে q-তে, কিন্তু তার পরে b আসেনি। abba: p → q → r, তারপর r থেকে বের হওয়া নেই। baab: p → p → q → q → r. ফাঁকা string-এ কোনো transition নেই, তাই p. State p মানে “এখনো a আসেনি”, q মানে “a এসেছে, তারপর ab হয়নি”, r মানে “ab পাওয়া গেছে”। তাই F = {r} ধরলে language হলো “ab substring হিসেবে আছে”। (দৈর্ঘ্য 12 পর্যন্ত পূর্ণ গণনায় আর CPython-এ চালিয়ে মেলানো।)
-
গণনা: Σ = {a, b, c}-এর ওপর ৩ state-এর কয়টি DFA আছে, (ক) start state q0 স্থির রাখলে, (খ) start state-ও বাছাই করতে দিলে? (খ)-এর যন্ত্রগুলো (ক)-এর চেয়ে বেশি ভিন্ন language দেয় কি?
- (ক) n = 3, k = 3: 39 · 23 = 19683 · 8 = 157464.
- (খ) তিন গুণ: 3 · 157464 = 472392.
- Language: বেশি নয়। Start state qi হলে q0 আর qi-এর নাম অদলবদল করলে start-স্থির একটি যন্ত্র পাওয়া যায়, যার language একই। তাই দুই ক্ষেত্রে ভিন্ন language-এর সেট হুবহু এক, আর সেই সংখ্যা 157464-এর চেয়ে অনেক কম, কারণ নাম অদলবদলেই বহু যন্ত্র একই language দেয়।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রম“DFA M ঠিক language L চেনে”, এই প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- প্রতিটি state-এর জন্য একটি বাক্য লেখা: সেখানে পৌঁছানো string-গুলোর ধর্ম (invariant)
- Base case: δ̂(q0, ε) = q0, আর ε q0-এর বাক্য মানে
- Hypothesis: দৈর্ঘ্য n-এর v-এর জন্য invariant সত্য ধরা
- প্রতিটি state আর শেষ চিহ্ন a-এর জন্য দেখানো যে δ(δ̂(q0, v), a) va-এর বাক্য মানে
- F-এর state-গুলোর বাক্য মিলিয়ে L(M) ⊆ L আর L ⊆ L(M) সিদ্ধান্ত
DFA M = (Q, Σ, δ, q0, F)-এর transition function δ কোন ধরনের?
- δ: Q × Σ → P(Q)
- δ: Q × Σ → Q, total function
- δ: Q × Σ∗ → Q
- δ: Q × Σ → Q, partial function, যেখানে না-থাকা ঘর মানে কিছু নয়
DFA-তে Q = {E, O}, Σ = {0, 1}, start E, F = {E}; δ(E, 0) = E, δ(E, 1) = O, δ(O, 0) = O, δ(O, 1) = E. δ̂(E, 0110) কী, আর 0110 গৃহীত কি?
- O, বাতিল
- O, গৃহীত
- E, গৃহীত
- E, বাতিল
Q = {q0, q1}, Σ = {0, 1} আর start state q0 স্থির রাখলে কয়টি ভিন্ন DFA (δ আর F-এর ভিন্ন বাছাই) আছে?
- 16
- 32
- 64
- 128
একটি DFA ফাঁকা string ε গ্রহণ করে ঠিক কখন?
- যখন start state q0 একটি accepting state
- যখন F = ∅
- যখন q0-এ প্রতিটি চিহ্নের self-loop আছে
- কখনো না, কারণ DFA-তে ε-transition নেই
একটি নির্দিষ্ট, স্থির DFA M-এর জন্য “w ∈ L(M)?” নির্ণয়ের সময় |w|-এর সাপেক্ষে কত?
- O(2|w|)
- O(|w|2)
- O(1)
- O(|w|)
একটি partial DFA-র প্রতিটি না-থাকা transition-এর গন্তব্য করা হলো একটি নতুন non-accepting state qd, আর qd-এর সব চিহ্নে আবার qd রাখা হলো। “না-থাকা transition মানে বাতিল” ব্যাখ্যার সঙ্গে তুলনায় language-এর কী হয়?
- বড় হয়: আটকে যাওয়া string এখন গৃহীত
- একই থাকে
- ছোট হয়: কিছু গৃহীত string এখন বাতিল
- Complement হয়ে যায়
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- সংজ্ঞা: DFA M = (Q, Σ, δ, q0, F), δ: Q × Σ → Q total; প্রতিটি state আর চিহ্নে ঠিক একটি পরের state.
- δ̂: δ̂(q, ε) = q, δ̂(q, wa) = δ(δ̂(q, w), a); আর δ̂(q, xy) = δ̂(δ̂(q, x), y), |y|-এর ওপর induction-এ প্রমাণিত।
- Language: L(M) = {w : δ̂(q0, w) ∈ F}; কোনো DFA যে language চেনে, সেটিই regular. ε গৃহীত ⇔ q0 ∈ F.
- Dead আর unreachable: Dead state যোগ করে partial ছবি সম্পূর্ণ হয়, language বদলায় না; unreachable state মুছলেও বদলায় না।
- খরচ আর গণনা: Membership O(|w|) সময়ে, স্থির স্মৃতিতে, তাই ADFA decidable; start স্থির রেখে n state, k চিহ্নের DFA nnk · 2nটি।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ০৪ · Theory of Computation-এর প্রমাণপুনরালোচনাInvariant আর |w|-এর ওপর induction-এ DFA-র সঠিকতা, বিস্তারিত।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ · Finite automatonপরিচয়DFA, NFA আর regex-এর প্রথম ঝলক।
- সফটওয়্যার টেস্টিং · পর্ব ১০ · State-transition testingপ্রয়োগState machine থেকে test case, বৈধ আর অবৈধ transition.
- কম্পিউটার আর্কিটেকচার · পর্ব ১৭ · FSM নকশাপাশের বিষয়Hardware-এ finite state machine, flip-flop দিয়ে।
- DSA · পর্ব ০৪ · Big-OপুনরালোচনাLinear time আর বৃদ্ধির হারের ভাষা।