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

Output-সহ automaton — Mealy আর Moore machine

Automata with Output — Moore and Mealy Machines, Their Equivalence, Sequence Detectors and the Serial Binary Adder

Taught in Bangla, this lesson extends finite automata with output. It defines Moore machines (output on states, n + 1 outputs) and Mealy machines (output on transitions, n outputs), designs a 101 detector with and without overlap, a parity generator and a two-state serial binary adder, and converts Moore to Mealy and Mealy to Moore with paired states (q, b). In-page Python (Pyodide) runs both models, performs the conversions and simulates the adder, and the page shows why no finite transducer can multiply serially.

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

  • Moore আর Mealy machine-এর ৬-tuple সংজ্ঞা, আর output string-এর দৈর্ঘ্যের পার্থক্য কেন হয়
  • “101” sequence detector-এর নকশা, overlap সহ ও ছাড়া, দুই মডেলেই
  • Moore ↔ Mealy রূপান্তরের দুটি theorem, প্রমাণসহ, আর প্রথম output-এর শর্ত
  • Serial binary adder-এর নকশা ও সঠিকতার প্রমাণ, আর serial গুণ কেন অসম্ভব
  • DFA, hardware FSM আর software state machine-এর সঙ্গে সম্পর্ক, Python আর JavaScript-এ চালিয়ে যাচাই

১ · হ্যাঁ/না-এর বদলে উত্তর — output-সহ যন্ত্র

লিফটের দুটি জিনিস লক্ষ করুন। দরজার ওপরের ডিসপ্লে দেখায় “৫”: এটি লিফটের অবস্থা, লিফট যতক্ষণ পাঁচতলায় আছে ততক্ষণ একই লেখা। আর বোতাম চাপলে যে “টুং” শব্দ হয়, সেটি একটি ঘটনার সাড়া: বোতাম না চাপলে শব্দ নেই, আর কোন বোতাম চাপা হলো তার ওপর শব্দ নির্ভর করে। প্রথমটি অবস্থার গায়ে লাগানো output, দ্বিতীয়টি ঘটনার গায়ে। এই পর্বের দুই যন্ত্র ঠিক এই দুই ধরনের: Moore machine ডিসপ্লের মতো, Mealy machine বোতামের শব্দের মতো।

পর্ব ০৭-এ (DFA-র ভিত্তি) যে DFA দেখেছেন, সে পুরো ইনপুট পড়ে শেষে একটিমাত্র উত্তর দেয়: গ্রহণ বা বাতিল। কিন্তু অনেক যন্ত্রের কাজ উত্তর দেওয়া নয়, অনুবাদ করা: প্রতিটি ইনপুট চিহ্নের সঙ্গে সঙ্গে কিছু একটা লেখা। সেন্সর লাইনের প্রতিটি বিটের পর parity বিট, একটি বিটের স্রোতে নির্দিষ্ট নকশা এলে সংকেত, দুটি সংখ্যার বিট পেলে যোগফলের বিট। এমন যন্ত্রের সাধারণ নাম finite-state transducer: ইনপুটের string থেকে output-এর string বানানোর সসীম যন্ত্র। এই পর্বে তার দুটি সবচেয়ে সরল, deterministic রূপ নিয়ে কাজ করব।

বাজারঘরের একটি (কাল্পনিক) চেকআউট কিয়স্ক দিয়ে শুরু করি। ইনপুটের চিহ্ন চারটি ঘটনা: a = পণ্য যোগ, c = চেকআউট, o = সঠিক OTP, x = বাতিল। কিয়স্কের চারটি state: E (কার্ট খালি), C (কার্টে পণ্য), P (OTP-র অপেক্ষা), D (অর্ডার নিশ্চিত)। প্রতিটি ঘটনায় কিয়স্ক পরের state-এ যায় আর গ্রাহককে একটি ছোট বার্তা দেখায়। ঘরে লেখা আছে “পরের state / বার্তা”:

stateacox
→ EC / যোগ হলোE / কার্ট খালিE / ভুল ধাপE / কার্ট খালি
CC / যোগ হলোP / OTP গেছেC / ভুল ধাপE / বাতিল
PP / আগে OTPP / OTP গেছেD / নিশ্চিতC / বাতিল
DC / যোগ হলোD / আগেই নিশ্চিতD / আগেই নিশ্চিতD / আগেই নিশ্চিত

এখানে বার্তা নির্ভর করে state আর ঘটনা দুটির ওপর: একই state C-তে a এলে “যোগ হলো”, x এলে “বাতিল”। এটি Mealy ধাঁচ। একই কিয়স্ককে Moore ধাঁচেও বানানো যায়: পর্দায় প্রতিটি state-এর একটি স্থির লেখা থাকবে, যেমন E-তে “কার্ট খালি”, P-তে “OTP দিন”। তখন output শুধু state-এর ওপর নির্ভর করে। লক্ষ করুন, table-এর ১৬টি ঘরই ভরা: DFA-র মতো এখানেও প্রতিটি state-এ প্রতিটি ঘটনার একটি ঘোষিত ফল আছে। Workflow হিসেবে এই ধরনের state machine পর্ব ২৪-এ আরও বিস্তারিত আসবে।

২ · Moore machine — output থাকে state-এর গায়ে

সংজ্ঞা ২.১ (Moore machine)

একটি Moore machine হলো একটি ৬-tuple M = (Q, Σ, Δ, δ, ω, q0), যেখানে

  1. Q সসীম state-এর সেট, Σ ইনপুটের alphabet, q0 ∈ Q start state;
  2. Δ একটি সসীম, অশূন্য output alphabet;
  3. δ: Q × Σ → Q একটি total transition function, ঠিক DFA-র মতো;
  4. ω: Q → Δ হলো output function: প্রতিটি state-এর গায়ে একটি output চিহ্ন।

ইনপুট w = a1a2…an-এর run r0, r1, …, rn (r0 = q0, ri = δ(ri−1, ai)) হলে M-এর output

TM(w) = ω(r0) ω(r1) … ω(rn) ∈ Δn+1

DFA-র সঙ্গে তুলনা করুন: Q, Σ, δ, q0 হুবহু এক। শুধু F-এর জায়গায় এসেছে Δ আর ω. যেখানে DFA বলত “এই state accepting কি না”, Moore machine বলে “এই state-এ পৌঁছালে কী লিখব”। TM (T মানে translation, অনুবাদ) প্রতিটি ইনপুট string-কে একটি output string দেয়, তাই যন্ত্রটি একটি function Σ∗ → Δ∗ হিসাব করে, একটি language নয়। Hopcroft–Ullman-এর মতো কিছু বইয়ে output function-কে λ লেখা হয়। এই কোর্সে কিছু বইয়ের ফাঁকা string-এর চিহ্ন হিসেবে λ-এর কথা আগেই বলা আছে, তাই বিভ্রান্তি এড়াতে আমরা ω লিখি।

সবচেয়ে গুরুত্বপূর্ণ খুঁটিনাটি হলো দৈর্ঘ্য। n চিহ্ন পড়লে run-এ n + 1টি state, তাই output-এ n + 1টি চিহ্ন। প্রথম চিহ্ন ω(q0) আসে কিছু পড়ার আগেই; ফাঁকা ইনপুটেও Moore machine একটি চিহ্ন লেখে: TM(ε) = ω(q0). লিফটের ডিসপ্লে কেউ বোতাম চাপার আগেও কিছু একটা দেখায়, ঠিক তেমন।

প্রথম উদাহরণ বাজারঘরের গুদামের সেই সেন্সর লাইন, যার parity check পর্ব ০৭-এ DFA দিয়ে করা হয়েছিল। এবার যন্ত্রটি প্রতিটি বিটের পর জানাবে এ পর্যন্ত parity কত: 1-এর সংখ্যা বিজোড় হলে 1, জোড় হলে 0. এটি একটি parity generator, আর DFA-র দুই state E ও O-তে output বসালেই পাওয়া যায়: ω(E) = 0, ω(O) = 1.

Parity generator — দুই state-এর Moore machine

বৃত্তের ভেতরে “state/output”. Accepting state নেই; প্রতিটি state নিজের output লেখে।

Moore parity generator: state E outputs 0, state O outputs 1 E/0O/1 11 00 জোড়: লেখে 0বিজোড়: লেখে 1
ছবি ১২.১ — Parity generator. ইনপুট 1011-এ run E, O, O, E, O, তাই output 01101: পাঁচটি চিহ্ন, চারটি ইনপুটের জন্য।

এবার একটু কঠিন কাজ: একটি sequence detector, যা বিটের স্রোতে “101” শেষ হওয়ার মুহূর্তে 1 লেখে, বাকি সময় 0. ধরা যাক মিলগুলো পরস্পরের ওপর পড়তে পারে, অর্থাৎ overlap চলে: 10101-এ দুটি মিল, অবস্থান ১–৩ আর ৩–৫. প্রতিটি state মনে রাখে নকশার কতটুকু এইমাত্র মিলেছে। Moore-এ “এইমাত্র পুরো 101 মিলল” কথাটিও একটি আলাদা state হতে হবে, কারণ output state-এর গায়ে:

stateঅর্থ: শেষে মিলেছে01ω
→ Aকিছুই নাAB0
B“1”CB0
C“10”AD0
D“101”, পুরো মিলCB1

D থেকে 0 এলে C-তে যাওয়াই overlap: “101”-এর শেষ 1-এর পরে 0 মানে শেষে “10” মিলেছে, যা নতুন মিলের শুরু। নিচের stepper 10101 পড়ে।

1start A, write ω(A) = 02read 1: A → B, write 03read 0: B → C, write 04read 1: C → D, write 15read 0: D → C, write 06read 1: C → D, write 17output 000101, 6 symbols
Run আর output
পড়া অংশ
state
এ পর্যন্ত output
  1. শুরু। কিছু পড়া হয়নি, তবু যন্ত্র A-তে আছে আর ω(A) = 0 লেখে। Output-এর এই প্রথম চিহ্নটি ইনপুটের ওপর নির্ভর করে না।
  2. প্রথম চিহ্ন 1. δ(A, 1) = B, ω(B) = 0. নকশার প্রথম ঘর মিলেছে, কিন্তু পুরো মিল হয়নি।
  3. দ্বিতীয় চিহ্ন 0. δ(B, 0) = C. শেষে “10” মিলেছে, এখনো output 0.
  4. তৃতীয় চিহ্ন 1. δ(C, 1) = D, ω(D) = 1. পড়া অংশ “101”, প্রথম মিল, output-এ প্রথম 1.
  5. চতুর্থ চিহ্ন 0. δ(D, 0) = C, ω(C) = 0. আগের মিলের শেষ 1 আর এই 0 মিলে শেষে “10”: overlap-এর জন্যই A নয়, C.
  6. পঞ্চম চিহ্ন 1. δ(C, 1) = D, আবার 1. অবস্থান ৩–৫-এ দ্বিতীয় মিল, যার প্রথম 1 আগের মিলের শেষ 1.
  7. ফল। TM(10101) = 000101: ৫টি ইনপুট চিহ্নে ৬টি output চিহ্ন। প্রথম 0 বাদ দিলে বাকি 00101-এর প্রতিটি অবস্থান বলে, ঠিক সেখানে 101 শেষ হয়েছে কি না।

৩ · Mealy machine — output থাকে তীরের গায়ে

সংজ্ঞা ৩.১ (Mealy machine)

একটি Mealy machine-ও একটি ৬-tuple M = (Q, Σ, Δ, δ, ω, q0), সব অংশ Moore-এর মতো, শুধু output function ω: Q × Σ → Δ. w = a1…an-এর run r0, …, rn হলে

TM(w) = ω(r0, a1) ω(r1, a2) … ω(rn−1, an) ∈ Δn

প্রতিটি transition একটি চিহ্ন পড়ে আর একটি চিহ্ন লেখে, তাই output-এর দৈর্ঘ্য ঠিক ইনপুটের দৈর্ঘ্য, আর TM(ε) = ε. State diagram-এ তীরের গায়ে “a/b” লেখা হয়, যার মানে “a পড়লে output b”. 101 detector-এর Mealy রূপে D state লাগে না, কারণ “পুরো মিল” কথাটি C থেকে 1 পড়ার তীরেই বলা যায়:

101 detector — তিন state-এর Mealy machine (overlap সহ)

তীরের গায়ে “ইনপুট/output”. একটিমাত্র তীরে output 1: S2 থেকে 1 পড়ার তীর।

Mealy machine detecting 101 with overlap S0S1S2 0/01/0 1/00/0 0/0 1/1
ছবি ১২.২ — S0 = “কিছুই মেলেনি”, S1 = “শেষে 1”, S2 = “শেষে 10”. লাল তীর overlap-এর নিয়ম: মিলের শেষ 1-কে নতুন শুরু ধরে S1-এ যাওয়া। Overlap না চাইলে এই তীর S0-তে যাবে।

ছবিতে দুটি জিনিস মিলিয়ে দেখুন। প্রথমত, প্রতিটি state থেকে 0 আর 1 দুটির ঠিক একটি করে তীর: δ total. দ্বিতীয়ত, Moore-এর চার state-এর জায়গায় এখানে তিনটি। এটি সাধারণ সত্য: Mealy machine কখনো Moore-এর চেয়ে বেশি state চায় না, প্রায়ই কম চায় (§৪)। নিচের ব্লক দুই যন্ত্রকে হাতে লেখা ছোট simulator-এ চালায়, তারপর দৈর্ঘ্য 0 থেকে 10-এর সব string-এ সংজ্ঞার সরল একটি predicate-এর সঙ্গে মেলায়: “অবস্থান i-তে শেষ হওয়া তিন চিহ্ন 101 কি না”। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def moore(M, w):                         # output length |w| + 1
    q = M["start"]; out = M["out"][q]
    for a in w:
        q = M["d"][q, a]
        out += M["out"][q]
    return out
def mealy(M, w):                         # output length |w|
    q, out = M["start"], ""
    for a in w:
        out += M["out"][q, a]
        q = M["d"][q, a]
    return out
T = lambda s: {(p, a): r for p, row in s.items() for a, r in zip("01", row)}
MOORE = {"start": "A", "out": {"A": "0", "B": "0", "C": "0", "D": "1"},
         "d": T({"A": "AB", "B": "CB", "C": "AD", "D": "CB"})}
MEALY = {"start": "S0", "d": T({"S0": ["S0", "S1"], "S1": ["S2", "S1"],
                               "S2": ["S0", "S1"]}),
         "out": T({"S0": "00", "S1": "00", "S2": "01"})}
w = "10101"
print("input       ", w)
print("Moore output", moore(MOORE, w), " length", len(moore(MOORE, w)))
print("Mealy output", " " + mealy(MEALY, w), " length", len(mealy(MEALY, w)))
def spec(w):                             # 1 where "101" ends (overlap allowed)
    return "".join("1" if w[max(0, i - 2):i + 1] == "101" else "0"
                   for i in range(len(w)))
n = bad = 0
for k in range(11):
    for t in product("01", repeat=k):
        s = "".join(t); n += 1
        bad += mealy(MEALY, s) != spec(s)
        bad += moore(MOORE, s) != "0" + spec(s)
print("strings up to length 10:", n, " mismatches:", bad)

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

input        10101
Moore output 000101  length 6
Mealy output  00101  length 5
strings up to length 10: 2047  mismatches: 0

Mealy-র output এক ঘর ডানে সরিয়ে ছাপা হয়েছে, যাতে প্রতিটি output তার ইনপুট চিহ্নের নিচে বসে। তখন দেখা যায়, Moore-এর output হুবহু Mealy-র output, শুধু সামনে একটি বাড়তি 0, যা ω(A). দৈর্ঘ্য 0 থেকে 10-এর ২০৪৭টি string-এর প্রতিটিতে Mealy-র output spec(w)-এর সমান, আর Moore-এর output “0” + spec(w)-এর সমান; একটিও অমিল নেই। §৪-এর সমতার সংজ্ঞা ঠিক এই সম্পর্ক।

Overlap সহ বনাম overlap ছাড়া

পরীক্ষায় প্রশ্নে প্রায়ই লেখা থাকে “overlapping” বা “non-overlapping”, আর এক শব্দে যন্ত্র বদলে যায়। Overlap ছাড়া মানে একটি মিলের চিহ্ন পরের মিলে আর গোনা যাবে না: 10101-এ মিল একটিই, কারণ দ্বিতীয় 101-এর প্রথম 1 আগের মিলে খরচ হয়ে গেছে। Mealy যন্ত্রে বদল শুধু লাল তীরে: S2 থেকে 1/1 পড়ে S1-এর বদলে S0-তে ফেরা। নিচের JavaScript ব্লক দুই নিয়মে একই ইনপুট চালিয়ে প্রতিটি transition ছাপে; w বদলে আবার চালিয়ে দেখুন।

// Mealy detector for "101": with and without overlap, one line per symbol.
// Change the input string w and press Run again.
const next = { S0: ["S0", "S1"], S1: ["S2", "S1"], S2: ["S0", "S1"] };
function detect(w, overlap) {
  let q = "S0", out = "";
  console.log(overlap ? "overlap allowed:" : "no overlap:");
  for (const a of w) {
    if (a !== "0" && a !== "1") return "input must be over {0,1}";
    const hit = q === "S2" && a === "1";      // the only transition with output 1
    let r = next[q][Number(a)];
    if (hit && !overlap) r = "S0";            // forget the final 1 after a match
    out += hit ? "1" : "0";
    console.log(`  ${q} --${a}/${hit ? 1 : 0}--> ${r}   output ${out}`);
    q = r;
  }
  return out;
}
const w = "1010101";
const ov = detect(w, true), no = detect(w, false);
const count = s => [...s].filter(c => c === "1").length;
console.log("input      ", w);
console.log("overlap    ", ov, " matches", count(ov));
console.log("no overlap ", no, " matches", count(no));

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

overlap allowed:
  S0 --1/0--> S1   output 0
  S1 --0/0--> S2   output 00
  S2 --1/1--> S1   output 001
  S1 --0/0--> S2   output 0010
  S2 --1/1--> S1   output 00101
  S1 --0/0--> S2   output 001010
  S2 --1/1--> S1   output 0010101
no overlap:
  S0 --1/0--> S1   output 0
  S1 --0/0--> S2   output 00
  S2 --1/1--> S0   output 001
  S0 --0/0--> S0   output 0010
  S0 --1/0--> S1   output 00100
  S1 --0/0--> S2   output 001000
  S2 --1/1--> S0   output 0010001
input       1010101
overlap     0010101  matches 3
no overlap  0010001  matches 2

দুই run প্রথম তিন চিহ্নে একই, তৃতীয় চিহ্নে প্রথম মিল। তারপর পথ আলাদা: overlap-এ যন্ত্র S1-এ যায় (“শেষে 1 আছে”), তাই অবস্থান ৫ আর ৭-এ আবার মিল, মোট ৩টি। Overlap ছাড়া যন্ত্র S0-তে ফিরে সব ভুলে যায়; চতুর্থ চিহ্ন 0 তাকে S0-তেই রাখে, তাই অবস্থান ৫-এ মিল হয় না, পরের মিল অবস্থান ৭-এ, মোট ২টি। দুই যন্ত্রেরই state তিনটি; নিয়ম বদলেছে শুধু একটি তীরের গন্তব্য।

৪ · দুই মডেলের সমতা — রূপান্তর আর প্রথম output-এর শর্ত

Moore-এর output-এ সবসময় একটি বাড়তি প্রথম চিহ্ন, তাই দুই যন্ত্রের output হুবহু সমান হতেই পারে না। সমতার সংজ্ঞায় তাই প্রথম চিহ্নটি আলাদা করে রাখা হয়, Hopcroft–Ullman-এর রীতিতে:

সংজ্ঞা ৪.১ (Moore আর Mealy-র সমতা)

একই Σ আর Δ-এর ওপর Moore machine M আর Mealy machine M′ সমতুল্য, যদি সব w ∈ Σ∗-এর জন্য

TM(w) = ωM(q0) · TM′(w)

অর্থাৎ Moore-এর প্রথম চিহ্ন বাদ দিলে বাকিটা Mealy-র output.

প্রথম চিহ্নটি ইনপুটের কোনো অংশের সাড়া নয়, যন্ত্রের “চালু হওয়ার মুহূর্তের” অবস্থা। এ জন্যই একে বাদ দিয়ে তুলনা করা যুক্তিসঙ্গত। এর একটি পরিণাম পরের theorem-এ দেখবেন: Mealy থেকে Moore বানালে প্রথম চিহ্নটি আমরা ইচ্ছামতো বাছতে পারি।

উপপাদ্য ৪.২ (Moore → Mealy)

প্রতিটি Moore machine M = (Q, Σ, Δ, δ, ω, q0)-এর জন্য একই state-এর একটি সমতুল্য Mealy machine M′ = (Q, Σ, Δ, δ, ω′, q0) আছে, যেখানে ω′(q, a) = ω(δ(q, a)).

প্রমাণ:

  1. M আর M′-এর δ আর q0 এক, তাই যেকোনো w = a1…an-এ দুই যন্ত্রের run একই r0, …, rn. — run-এর সংজ্ঞা শুধু δ আর q0-এর ওপর নির্ভর করে
  2. M′-এর i-তম output ω′(ri−1, ai) = ω(δ(ri−1, ai)) = ω(ri), প্রতিটি 1 ≤ i ≤ n-এ। — ω′-এর সংজ্ঞা আর ri-এর সংজ্ঞা
  3. তাই TM′(w) = ω(r1)…ω(rn), আর TM(w) = ω(r0) ω(r1)…ω(rn) = ω(q0) · TM′(w). ∎

কথায়: Moore যে চিহ্ন একটি state-এ ঢুকে লেখে, Mealy সেটিই লেখে সেই state-এ ঢোকার তীরে। উল্টো দিকটি কঠিন, কারণ Mealy-তে একই state-এ ঢোকার বিভিন্ন তীরে বিভিন্ন output থাকতে পারে। 101 detector-এ S1-এ ঢোকে 1/0 তীর (S0 আর S1 থেকে) আর 1/1 তীর (S2 থেকে)। Moore-এ একটি state-এর একটিই output, তাই S1-কে দুই ভাগ করতে হবে: “S1, শেষ output 0” আর “S1, শেষ output 1”.

উপপাদ্য ৪.৩ (Mealy → Moore)

Mealy machine M = (Q, Σ, Δ, δ, ω, q0) আর যেকোনো b0 ∈ Δ-এর জন্য M′ = (Q × Δ, Σ, Δ, δ′, ω′, (q0, b0)) একটি সমতুল্য Moore machine, যেখানে

δ′((q, b), a) = (δ(q, a), ω(q, a))   এবং   ω′((q, b)) = b

M′-এর state বড়জোর |Q| · |Δ|টি; শুধু start থেকে পৌঁছানো জোড়গুলো রাখলেই চলে।

প্রমাণ (দৈর্ঘ্যের ওপর induction, পর্ব ০৪-এর ছাঁচে)। w = a1…an, M-এর run r0, …, rn, আর M′-এর run s0, …, sn.

  1. Claim: s0 = (q0, b0), আর প্রতিটি 1 ≤ i ≤ n-এ si = (ri, ω(ri−1, ai)). বিশেষত সব i-তে si-এর প্রথম অংশ ri. — invariant
  2. Base: s0 = (q0, b0), যার প্রথম অংশ r0 = q0. — M′-এর start state
  3. Step: si−1-এর প্রথম অংশ ri−1 ধরে নিই (দ্বিতীয় অংশ যা-ই হোক)। তখন si = δ′(si−1, ai) = (δ(ri−1, ai), ω(ri−1, ai)) = (ri, ω(ri−1, ai)). — δ′-এর সংজ্ঞা; δ′ দ্বিতীয় অংশ ব্যবহারই করে না
  4. Output: ω′(s0) = b0, আর i ≥ 1-এ ω′(si) = ω(ri−1, ai), যা M-এর i-তম output. তাই TM′(w) = b0 · TM(w), আর ω′(s0) = b0, ঠিক সংজ্ঞা ৪.১. — ω′-এর সংজ্ঞা
  5. State-এর সেট Q × Δ, যার আকার |Q| · |Δ|. যে জোড়ে কোনো run পৌঁছায় না, তা মুছলে কোনো output বদলায় না। ∎

এখানে দ্বিতীয় অংশ b একটি “স্মৃতির খাতা”: এইমাত্র কোন output লেখা হয়েছিল। Moore যন্ত্রটি ঠিক সেই চিহ্নটিই আবার নিজের output হিসেবে দেখায়। কোন জোড়গুলো সত্যিই লাগে, তা বের করার কৌশল পর্ব ১০-এর (NFA থেকে DFA) lazy subset construction-এর মতো: start থেকে BFS, নতুন জোড় এলে সারিতে যোগ। নিচের stepper 101 detector-এর Mealy রূপকে Moore-এ রূপান্তর করে, b0 = 0 নিয়ে।

Moore state01ω′নতুন নাম
→ (S0, 0)(S0, 0)(S1, 0)0A
(S1, 0)(S2, 0)(S1, 0)0B
(S2, 0)(S0, 0)(S1, 1)0C
(S1, 1)(S2, 0)(S1, 0)1D
  1. কাঠামো। নতুন state হবে জোড় (q, b), q ∈ {S0, S1, S2}, b ∈ {0, 1}: সম্ভাব্য ৬টি। Start (S0, 0), কারণ b0 = 0 বেছেছি। BFS-এর সারিতে শুধু এটি।
  2. (S0, 0) প্রক্রিয়া। 0: Mealy-তে S0 থেকে 0/0 যায় S0-তে, তাই (S0, 0), পুরোনো। 1: 1/0 যায় S1-এ, তাই (S1, 0), নতুন, সারিতে যোগ। ω′ = 0.
  3. (S1, 0) প্রক্রিয়া। 0: 0/0 যায় S2-তে, তাই (S2, 0), নতুন। 1: 1/0 যায় S1-এ, তাই (S1, 0), নিজেই। ω′ = 0.
  4. (S2, 0) প্রক্রিয়া। 0: 0/0 যায় S0-তে, তাই (S0, 0). 1: এটি লাল তীর 1/1, যায় S1-এ, তাই (S1, 1), নতুন: S1 এখানে ভাগ হলো।
  5. (S1, 1) প্রক্রিয়া। δ′ দ্বিতীয় অংশ দেখে না, তাই এর তীর (S1, 0)-এর মতোই: 0-তে (S2, 0), 1-এ (S1, 0). কোনো নতুন জোড় নেই, সারি ফাঁকা। ω′ = 1.
  6. ফল। ৪টি state; (S0, 1) আর (S2, 1)-এ কখনো পৌঁছানো যায় না, কারণ S0 বা S2-তে ঢোকার কোনো তীরে output 1 নেই। নাম A, B, C, D দিলে এটি হুবহু §২-এর হাতে বানানো Moore table.

নিচের ব্লকে দুটি রূপান্তরই function হিসেবে লেখা। এটি তিনটি Mealy যন্ত্র নেয়: overlap সহ ও ছাড়া 101 detector, আর §৫-এর serial adder; প্রতিটিকে Moore-এ নেয়, তারপর সেই Moore-কে আবার Mealy-তে। দুই ধাপের ফল মূলের সঙ্গে সব ছোট ইনপুটে মেলানো হয়: binary যন্ত্রে দৈর্ঘ্য 8 পর্যন্ত, চার চিহ্নের adder-এ দৈর্ঘ্য 6 পর্যন্ত।

from itertools import product
def mealy(M, w):
    q, out = M["start"], []
    for a in w: out.append(M["out"][q, a]); q = M["d"][q, a]
    return out
def moore(M, w):
    q = M["start"]; out = [M["out"][q]]
    for a in w: q = M["d"][q, a]; out.append(M["out"][q])
    return out
def mealy_to_moore(M, sigma, b0="0"):    # states (q, b), reachable only
    start = (M["start"], b0); d, out, todo = {}, {start: b0}, [start]
    while todo:
        q, b = p = todo.pop(0)
        for a in sigma:
            r = d[p, a] = (M["d"][q, a], M["out"][q, a])
            if r not in out:
                out[r] = r[1]; todo.append(r)
    return {"start": start, "d": d, "out": out}
def moore_to_mealy(M):                   # same states, output of the target
    return {"start": M["start"], "d": M["d"],
            "out": {k: M["out"][r] for k, r in M["d"].items()}}
T = lambda s, sig: {(p, a): r for p, row in s.items() for a, r in zip(sig, row)}
OV = {"start": "S0", "d": T({"S0": ["S0", "S1"], "S1": ["S2", "S1"],
      "S2": ["S0", "S1"]}, "01"), "out": T({"S0": "00", "S1": "00", "S2": "01"}, "01")}
NON = {"start": "S0", "d": {**OV["d"], ("S2", "1"): "S0"}, "out": OV["out"]}
P = ["00", "01", "10", "11"]             # serial adder: pairs (a_i, b_i)
ADD = {"start": 0, "d": {(c, p): (int(p[0]) + int(p[1]) + c) // 2 for c in (0, 1) for p in P},
       "out": {(c, p): str((int(p[0]) + int(p[1]) + c) % 2) for c in (0, 1) for p in P}}
for name, M, sig, n in [("overlap", OV, "01", 8), ("no-overlap", NON, "01", 8), ("adder", ADD, P, 6)]:
    N = mealy_to_moore(M, sig); B = moore_to_mealy(N)
    words = [w for k in range(n + 1) for w in product(sig, repeat=k)]
    ok1 = all(moore(N, w) == ["0"] + mealy(M, w) for w in words)
    ok2 = all(mealy(B, w) == mealy(M, w) for w in words)
    print(f"{name}: {len(M['d'])//len(sig)} -> {len(N['out'])} states, {len(words)} inputs, {ok1}, {ok2}")
print("Moore states (overlap):", list(mealy_to_moore(OV, "01")["out"]))

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

overlap: 3 -> 4 states, 511 inputs, True, True
no-overlap: 3 -> 4 states, 511 inputs, True, True
adder: 2 -> 4 states, 5461 inputs, True, True
Moore states (overlap): [('S0', '0'), ('S1', '0'), ('S2', '0'), ('S1', '1')]

প্রতিটি লাইনে চারটি তথ্য: Mealy-র state থেকে Moore-এর state (৩ থেকে ৪, ৩ থেকে ৪, ২ থেকে ৪), কতগুলো ইনপুটে মেলানো হয়েছে (দৈর্ঘ্য 8 পর্যন্ত ৫১১টি binary string; দৈর্ঘ্য 6 পর্যন্ত ৫৪৬১টি বিট-জোড়ের ক্রম), প্রথম True মানে Moore-এর output = “0” + Mealy-র output, আর দ্বিতীয় True মানে Moore থেকে ফেরা Mealy মূলের সঙ্গে হুবহু মেলে। শেষ লাইন stepper-এর চারটি জোড়, একই BFS ক্রমে। Adder-এ দুটি state থেকে চারটি: এখানে |Q| · |Δ| = 2 · 2 = 4, অর্থাৎ ওপরের সীমা পুরোপুরি লেগেছে। মনে রাখুন, এই মিল সসীম দৈর্ঘ্য পর্যন্ত; সব দৈর্ঘ্যের নিশ্চয়তা দেয় উপপাদ্য ৪.২ আর ৪.৩-এর প্রমাণ।

একটি সূক্ষ্ম কথা: Moore → Mealy-তে state একই থাকে, কিন্তু Mealy → Moore-এ বাড়তে পারে। তাই একটি কাজের জন্য সবচেয়ে ছোট Mealy যন্ত্র কখনো সবচেয়ে ছোট Moore যন্ত্রের চেয়ে বড় নয়। সবচেয়ে সরল উদাহরণ “copy machine”, যা প্রতিটি ইনপুট বিট হুবহু লেখে: Mealy-তে এক state যথেষ্ট (0/0 আর 1/1 দুটি self-loop), কিন্তু এক state-এর Moore machine সবসময় একই চিহ্ন লেখে, তাই Moore-এ অন্তত দুটি state লাগে (অনুশীলন ২)।

৫ · Serial binary adder — Mealy machine দিয়ে যোগ

খাতায় দুটি সংখ্যা যোগ করার সময় আপনি ডান দিক থেকে শুরু করেন, প্রতিটি কলামে দুটি অঙ্ক আর “হাতে” থাকা সংখ্যাটি যোগ করেন, একটি অঙ্ক লেখেন আর নতুন “হাতে” রাখেন। পুরো সংখ্যা মনে রাখার দরকার হয় না; মনে রাখতে হয় শুধু হাতে কত। Binary-তে হাতে থাকে 0 বা 1, তাই এই পদ্ধতিটি দুই state-এর একটি যন্ত্র।

Serial binary adder ইনপুট হিসেবে পড়ে বিট-জোড় (ai, bi), সবচেয়ে কম গুরুত্বের বিট (least significant bit, LSB) থেকে শুরু করে। তাই Σ = {(0,0), (0,1), (1,0), (1,1)}, চারটি চিহ্ন; Δ = {0, 1}. State Q = {C0, C1}: হাতে carry 0 বা 1; start C0. প্রতিটি ধাপ একটি full adder-এর হিসাব:

output si = ai ⊕ bi ⊕ ci   এবং   পরের carry ci+1 = majority(ai, bi, ci)

এখানে ⊕ মানে XOR (দুটি বিট আলাদা হলে 1), আর majority মানে তিনটির মধ্যে অন্তত দুটি 1 হলে 1. Output নির্ভর করে carry (state) আর এইমাত্র পড়া জোড় (ইনপুট) দুটির ওপর, তাই এটি স্বাভাবিকভাবেই একটি Mealy machine: serial adder. নিচের stepper 6 + 7 যোগ করে, চার বিটে: 6 = 0110, 7 = 0111, LSB থেকে জোড়গুলো (0,1), (1,1), (1,1), (0,0).

1start C0 (carry 0)2bit 0: (0,1)+0 = 1 → out 1, C03bit 1: (1,1)+0 = 2 → out 0, C14bit 2: (1,1)+1 = 3 → out 1, C15bit 3: (0,0)+1 = 1 → out 1, C06LSB first 1011 = 1101 = 13
যন্ত্রের অবস্থা
পড়া জোড়
state (carry)
output, LSB আগে
এ পর্যন্ত মান
  1. শুরু। State C0: হাতে কিছু নেই। Mealy যন্ত্র কিছু পড়ার আগে কিছু লেখে না, output ε.
  2. বিট 0. জোড় (0, 1), carry 0: যোগফল 1, তাই output 1, carry 0, state C0. এ পর্যন্ত output-এর মান 1, যা 6 আর 7-এর শেষ বিট দুটির যোগফল 0 + 1.
  3. বিট 1. জোড় (1, 1), carry 0: যোগফল 2 = binary 10, তাই output 0, carry 1, state C1. লেখা বিটগুলোর মান 1, আর হাতের carry-র মূল্য 4: মোট 5 = (6 mod 4) + (7 mod 4) = 2 + 3. “এ পর্যন্ত মান”-এর সারিতে carry-সহ হিসাব দেখানো আছে।
  4. বিট 2. জোড় (1, 1), carry 1: যোগফল 3 = binary 11, output 1, carry 1, state C1. লেখা বিট 101 (LSB আগে) মানে 5, আর carry-র মূল্য 8: মোট 13.
  5. বিট 3. জোড় (0, 0), carry 1: যোগফল 1, output 1, carry 0, state C0. লেখা চার বিটের মান 1 + 4 + 8 = 13, হাতে আর কিছু নেই।
  6. ফল। Output LSB আগে 1011; উল্টো দিক থেকে পড়লে 1101 = 13 = 6 + 7. শেষ carry 0, তাই বাড়তি বিট লাগেনি। দুই state-এর যন্ত্র যেকোনো দৈর্ঘ্যের সংখ্যা যোগ করে।
উপপাদ্য ৫.১ (serial adder সঠিক)

x, y < 2n হলে, তাদের n বিটের জোড়ের পরে একটি বাড়তি (0, 0) জোড় দিলে serial adder-এর n + 1টি output বিট s0…sn (LSB আগে) ঠিক x + y-এর binary রূপ।

  1. Invariant: i জোড় পড়ার পর state ci হলে, Σj<i sj2j + ci2i = (x mod 2i) + (y mod 2i). — stepper-এর “এ পর্যন্ত মান” সারি
  2. Base i = 0: বাম দিক 0 + 0, ডান দিক 0 + 0. — c0 = 0
  3. Step: i-তে invariant সত্য ধরি। Full adder-এর অভেদ si + 2ci+1 = ai + bi + ci-কে 2i দিয়ে গুণ করে বসালে Σj≤i sj2j + ci+12i+1 = Σj<i sj2j + ci2i + (ai + bi)2i = (x mod 2i+1) + (y mod 2i+1). — hypothesis; XOR আর majority-র সত্যসারণির আটটি ক্ষেত্র; x mod 2i+1 = x mod 2i + ai2i
  4. i = n + 1-এ ডান দিক x + y, কারণ x, y < 2n. আবার x + y < 2n+1 আর বাম দিকের যোগফল ঋণাত্মক নয়, তাই cn+1 = 0, অর্থাৎ Σj≤n sj2j = x + y. ∎

প্রমাণের ধাপ ৪-এ বাড়তি জোড়টি কেন লাগে, তা 11 + 5 = 16 দেখলেই বোঝা যায়: চার বিটের output 0000, শেষ carry 1, আর পঞ্চম জোড় (0, 0) সেই carry-কে বিট হিসেবে লেখায় (অনুশীলন ৩)। নিচের ব্লক adder-কে carry-র দুটি সূত্রে লেখে, 6 + 7-এর প্রতিটি ধাপ ছাপে, তারপর 0 থেকে 255-এর সব জোড়ে Python-এর সাধারণ যোগের সঙ্গে মেলায়।

def add_serial(x, y, nbits, trace=False):
    c, out = 0, []                       # state = carry (0 or 1)
    for i in range(nbits):               # least significant bit first
        a, b = (x >> i) & 1, (y >> i) & 1
        s = a ^ b ^ c                    # output: the sum bit
        c2 = (a & b) | (a & c) | (b & c) # next state: majority = carry out
        if trace:
            print(f"  bit {i}: in ({a},{b})  carry {c} -> out {s}, carry {c2}")
        out.append(s); c = c2
    return out, c
out, c = add_serial(6, 7, 4, trace=True)
print("output LSB first:", "".join(map(str, out)), " final carry:", c)
print("read MSB first:", "".join(map(str, out[::-1])), "=", int("".join(map(str, out[::-1])), 2))
bad = 0                                  # every pair of 8-bit numbers
for x in range(256):
    for y in range(256):
        bits, _ = add_serial(x, y, 9)    # one extra (0,0) pair for the carry
        bad += sum(b << i for i, b in enumerate(bits)) != x + y
print("8-bit pairs checked:", 256 * 256, " wrong sums:", bad)

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

  bit 0: in (0,1)  carry 0 -> out 1, carry 0
  bit 1: in (1,1)  carry 0 -> out 0, carry 1
  bit 2: in (1,1)  carry 1 -> out 1, carry 1
  bit 3: in (0,0)  carry 1 -> out 1, carry 0
output LSB first: 1011  final carry: 0
read MSB first: 1101 = 13
8-bit pairs checked: 65536  wrong sums: 0

চারটি লাইন stepper-এর চার ধাপের সঙ্গে হুবহু মেলে: carry-র ক্রম 0, 0, 1, 1, 0 আর output 1, 0, 1, 1. উল্টো করে পড়লে 1101 = 13. শেষ অংশে ৮ বিটের ৬৫৫৩৬টি জোড়ের প্রত্যেকটিতে ৯টি জোড় (একটি বাড়তি) পড়ে output-এর মান x + y-এর সঙ্গে মেলানো হয়েছে, আর একটিতেও ভুল যোগফল আসেনি।

যা সসীম যন্ত্র পারে না: serial গুণ

যোগ দুই state-এ হয়ে গেল। গুণ? খাতায় গুণ করতে আংশিক গুণফলের সারিগুলো মনে রাখতে হয়, আর তাদের সংখ্যা ইনপুটের সঙ্গে বাড়ে। এই অনুভূতিটি একটি theorem.

উপপাদ্য ৫.২

এমন কোনো Mealy machine নেই, যা যেকোনো x, y-এর বিট-জোড় LSB আগে পড়ে (দরকারি সংখ্যক বাড়তি (0, 0) জোড়সহ) x · y-এর বিট LSB আগে লেখে।

প্রমাণের রূপরেখা (বিরোধ দিয়ে)। ধরুন k state-এর এমন যন্ত্র M আছে। একটি n বেছে নিন, যাতে 2n−1 > k.

  1. x = 2n−1 (n বিটে শুধু শেষ বিট 1) আর y যেকোনো জোড় n-বিট সংখ্যা নিন; এমন y আছে 2n−1টি। — ইনপুট বাছাই
  2. x · y = y · 2n−1. y জোড় বলে এর নিচের n বিট সব 0, তাই প্রথম n জোড় পড়ার সময় প্রতিটি y-তে M একই output 0…0 লেখে। — 2n−1 দিয়ে গুণ মানে বাঁয়ে সরানো
  3. এরপর শুধু (0, 0) জোড় আসে, আর M-কে লিখতে হয় গুণফলের বাকি বিটগুলো, অর্থাৎ y-এর বিট 1 থেকে n − 1. ভিন্ন জোড় y-তে এই অংশ ভিন্ন। — y জোড়, তাই y-কে নির্ধারণ করে বিট 1…n−1
  4. M deterministic, তাই n জোড়ের পরে একই state থেকে একই বাকি ইনপুটে একই output আসে। তাই 2n−1টি y-এর প্রত্যেকটি আলাদা state-এ পৌঁছায়, অর্থাৎ অন্তত 2n−1 > k state, বিরোধ। ∎

যুক্তিটি পর্ব ০৪-এর distinguishable string-এর যুক্তির output-সংস্করণ: দুটি prefix-এর “ভবিষ্যৎ আচরণ” আলাদা হলে তাদের state আলাদা হতেই হবে। পর্ব ১৮-এ একই ধারণা Myhill–Nerode theorem হয়ে ফিরবে। (scratch-এ n = 5-এ পূর্ণ গণনায় দেখা গেছে, ১৬টি y-এর ভবিষ্যৎ output ১৬ রকম।)

৬ · DFA, hardware আর software — কোথায় কোন মডেল

DFA একটি বিশেষ Moore machine. একটি DFA (Q, Σ, δ, q0, F)-কে Moore machine বানান Δ = {0, 1} আর ω(q) = 1 যদি q ∈ F, নইলে 0 নিয়ে। তখন T(w)-এর শেষ চিহ্ন বলে w গৃহীত কি না, আর পুরো output বলে w-এর প্রতিটি prefix গৃহীত কি না। প্রথম চিহ্ন ω(q0) বলে ε গৃহীত কি না। Mealy রূপে (উপপাদ্য ৪.২) এই শেষ তথ্যটি হারায়, কারণ T(ε) = ε: Mealy machine ফাঁকা ইনপুটে কিছুই বলতে পারে না। প্রথম output-এর শর্তটি তাই শুধু আনুষ্ঠানিকতা নয়; ε-এর গ্রহণ ঠিক ওই চিহ্নেই থাকে।

Hardware-এ সময়ের পার্থক্য। Digital circuit-এ finite state machine বানানো হয় একটি state register (কয়েকটি flip-flop) আর দুই টুকরো logic দিয়ে। একটি synchronous circuit-এ state বদলায় শুধু clock-এর ধারে। Moore output state register থেকে আসে, তাই একটি ইনপুটের সাড়া output-এ দেখা যায় পরের clock-এর পরে: এক clock দেরি, কিন্তু output স্থির, ইনপুটের ঝাঁকুনি সরাসরি output-এ যায় না। Mealy output state আর ইনপুট দুটি থেকে সরাসরি logic দিয়ে আসে, তাই একই clock-এ সাড়া দেয়, কিন্তু ইনপুট বদলালে clock-এর মাঝখানেও output বদলাতে পারে। বিমূর্ত মডেলে এই দেরি দেখা যায় Moore-এর বাড়তি প্রথম চিহ্ন হিসেবে: একই অবস্থানে বসালে Moore-এর output এক ঘর ডানে সরে থাকে, যেমন §৩-এর ব্লকে দেখেছেন। Flip-flop, state assignment আর Verilog-এ এই নকশার পুরো প্রক্রিয়া কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ১৭-এ আছে; এখানে আমরা গাণিতিক দিকটুকু নিলাম।

Software-এ। চেকআউট কিয়স্কের মতো workflow, network protocol-এর connection, UI-এর বোতাম: এগুলো সাধারণত Mealy ধাঁচে লেখা হয়, কারণ প্রোগ্রামে “ঘটনা এলে কাজ করো আর পরের অবস্থায় যাও” স্বাভাবিক। পর্দার স্থির লেখা (“OTP দিন”) Moore ধাঁচ। Software testing-এ এমন যন্ত্রের প্রতিটি transition, আর বিশেষত অবৈধ transition, পরীক্ষা করার কৌশল সফটওয়্যার টেস্টিং কোর্সের পর্ব ১০-এ। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৪-এ এই দুই যন্ত্রের সংক্ষিপ্ত পরিচয় আছে।

বিষয়MooreMealy
Output functionω: Q → Δω: Q × Σ → Δ
দৈর্ঘ্য n-এর ইনপুটে outputn + 1টি চিহ্নnটি চিহ্ন
ফাঁকা ইনপুটেω(q0)ε
ছবিতে outputবৃত্তের ভেতরে “q/b”তীরের গায়ে “a/b”
State-এর সংখ্যাMealy থেকে বড়জোর |Q| · |Δ|Moore থেকে একই |Q|
Hardware-এ সাড়াপরের clock-এ, স্থিরএকই clock-এ, ঝাঁকুনি সম্ভব

সাধারণ ভুল

ভুলকেন ভুল, কী করবেন
Moore-এর output-কে n চিহ্নের ধরাRun-এ n + 1টি state; প্রথম চিহ্ন ω(q0) গুনুন
Mealy → Moore-এ একই state রাখাযে state-এ ভিন্ন output-এর তীর ঢোকে, তাকে (q, b) জোড়ে ভাগ করুন
Overlap নিয়ম না পড়ে detector বানানোমিলের পরের তীরের গন্তব্য নিয়মটির ওপর নির্ভর করে; প্রশ্নে খুঁজুন
Detector-এ ভুল “ফেরা”: 1011-এর পরে সব ভুলে শুরুতে যাওয়ামিল ভাঙলে নকশার যে অংশ এখনো শেষে মেলে, সেই state-এ যান (পর্ব ২৩-এর KMP ধারণা)
Serial adder-এ শেষ carry ভুলে যাওয়াএকটি বাড়তি (0, 0) জোড় দিন, নইলে 11 + 5-এর উত্তর 0 হয়
কিছু ঘর খালি রাখাδ total, আর Mealy-তে ω-ও প্রতিটি (q, a)-তে সংজ্ঞায়িত

আরও গভীরে: Mealy machine-এর সাধারণ রূপ হলো nondeterministic finite-state transducer, যার তীরে একটি চিহ্ন পড়ে একটি string লেখা যায়; এরা যে string-জোড়ের সম্পর্ক বর্ণনা করে, তাদের বলা হয় regular (বা rational) relation. Deterministic যন্ত্রের সমতা decidable, কিন্তু সাধারণ nondeterministic transducer-এর সমতা undecidable বলে ১৯৬০–৭০-এর দশকের গবেষণায় প্রমাণিত হয়েছে, আর regular relation intersection-এ বন্ধ নয়। ভাষা-প্রক্রিয়ায় শব্দের রূপতত্ত্ব (যেমন মূল শব্দ আর বিভক্তি আলাদা করা) আর speech recognition-এ weighted finite-state transducer বহু বছর ধরে ব্যবহৃত, যার একটি পরিচিত open-source library OpenFst.

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এমন প্রশ্ন প্রায়ই আসে:

  • Moore আর Mealy-র মূল পার্থক্য? Moore-এ ω: Q → Δ, n + 1টি output; Mealy-তে ω: Q × Σ → Δ, nটি output.
  • Mealy থেকে Moore-এ state সর্বোচ্চ কত হয়? |Q| · |Δ|, state (q, b) জোড়।
  • Overlapping “101” detector-এ কয়টি state? Mealy-তে ৩টি, Moore-এ ৪টি।
  • Serial binary adder-এর state কী মনে রাখে? শুধু carry, তাই দুটি state.
  • সসীম Mealy machine কি serial গুণ করতে পারে? না; ভবিষ্যৎ output-এর যুক্তিতে অসীম state লাগে।

৭ · AI-এর যুগে — AI-এর আঁকা Mealy/Moore যন্ত্র যাচাই

“101 detector-এর Moore machine দাও” ধরনের প্রশ্নে AI সহকারী দ্রুত একটি table দেয়, আর বেশিরভাগ সময় সেটি প্রায় ঠিক। কিন্তু “প্রায়” এখানে বিপজ্জনক: একটি তীরের ভুল গন্তব্য overlap-এর নিয়ম বদলে দেয়, আর তা ছোট কয়েকটি উদাহরণে ধরা পড়ে না। এই বিষয়ে কয়েকটি ভুল বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
Overlap চাওয়া হয়েছে, অথচ মিলের পরে start-এ ফেরা (বা উল্টোটা)10101 আর 1010101 চালান; overlap-এ ২টি আর ৩টি মিল হওয়ার কথা
Moore-এর output n চিহ্নের বলা, বা প্রথম চিহ্ন বাদ দিয়ে তুলনা না বলাদৈর্ঘ্য গুনুন: Moore-এ n + 1; সংজ্ঞা ৪.১-এর মতো সমতা লিখতে বলুন
Mealy → Moore-এ state ভাগ না করা, বা সব |Q| · |Δ| জোড় অকারণে রাখাপ্রতিটি state-এ ঢোকা তীরের output দেখুন; BFS-এ শুধু পৌঁছানো জোড় রাখুন
Table-এ কিছু ঘর খালিঘর গুনুন: δ আর Mealy-র ω দুটিরই |Q| · |Σ|টি ঘর
সঠিকতার “প্রমাণ” শুধু একটি উদাহরণপ্রতিটি state-এর অর্থ (invariant) আর দৈর্ঘ্যের ওপর induction চান
বানানো ইতিহাস, যেমন ভুল সাল বা প্রবন্ধের নামHopcroft–Ullman বা Sipser-এর মতো বিশ্বস্ত বই আর মূল প্রবন্ধে মেলান

AI-এর কাছে output-সহ যন্ত্র চাইলে এমনভাবে চান, যাতে উত্তর নিজেই যাচাইযোগ্য হয়:

Σ = {0, 1}-এর ওপর এই কাজের একটি Mealy machine আর একটি Moore machine দাও: [যেমন "বিটের স্রোতে 110 শেষ হলেই output 1, overlap চলবে"] ১. দুটির ৬-tuple (Q, Σ, Δ, δ, ω, q0) লেখো, আর δ ও ω সম্পূর্ণ table হিসেবে দাও; কোনো ঘর খালি রাখবে না। ২. প্রতিটি state কী মনে রাখে, এক লাইনে বলো (invariant). ৩. দৈর্ঘ্য n-এর ইনপুটে প্রতিটি যন্ত্র কয়টি output চিহ্ন দেয়, আর দুটিকে কীভাবে তুলনা করতে হয় (Moore-এর প্রথম চিহ্ন), স্পষ্ট বলো। ৪. Mealy থেকে Moore রূপান্তর (q, b) জোড় দিয়ে ধাপে ধাপে দেখাও, শুধু পৌঁছানো জোড় রেখে। ৫. শুধু itertools দিয়ে দৈর্ঘ্য 10 পর্যন্ত সব string-এ দুটি যন্ত্রকে একটি সরল Python predicate-এর সঙ্গে মেলানোর কোড দাও। ৬. কোনো সাল, নাম বা প্রবন্ধে নিশ্চিত না হলে স্পষ্ট বলো।

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

পাল্টা-উদাহরণ পেলে সেটিই AI-কে ফেরত দিন (“এই যন্ত্র 1010101-এ দুটি মিল দেখায়, overlap-এ তিনটি হওয়ার কথা”)। নির্দিষ্ট একটি ইনপুট দেখালে AI সাধারণত ভুলটি দ্রুত ঠিক করে। কিন্তু গণনা শুধু সসীম অংশের নিশ্চয়তা দেয়; সব দৈর্ঘ্যের জন্য invariant আর প্রমাণই ভরসা।

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

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

প্র ০১Mealy আর Moore দুজনের নামে দুটি যন্ত্র। ১৯৫০-এর দশকের কোন প্রশ্ন থেকে এই মডেল দুটি এসেছিল?

১৯৫০-এর দশকের শুরুতে টেলিফোন এক্সচেঞ্জ আর প্রথম দিকের কম্পিউটারে relay আর vacuum tube-এর বিশাল switching circuit ছিল। এদের অনেকগুলো “sequential”: output শুধু বর্তমান ইনপুটের ওপর নয়, অতীতের ওপরও নির্ভর করে। প্রকৌশলীদের প্রশ্ন ছিল, এমন circuit-এর আচরণ কাগজে কীভাবে লেখা যায়, আর একটি লিখিত আচরণ থেকে কীভাবে নিয়ম মেনে circuit বানানো যায়।

David Huffman ১৯৫৪ সালে sequential switching circuit নকশার একটি পদ্ধতি প্রকাশ করেন, যেখানে state আর flow table-এর ধারণা স্পষ্ট। Bell Labs-এর George Mealy ১৯৫৫ সালে Bell System Technical Journal-এ “A Method for Synthesizing Sequential Circuits” প্রকাশ করেন। Edward Moore ১৯৫৬ সালের “Automata Studies” সংকলনে “Gedanken-experiments on Sequential Machines” লেখেন। তবে ইতিহাসবিদ আর পাঠ্যবইয়ের লেখকেরা প্রায়ই মনে করিয়ে দেন যে আজকের পরিচ্ছন্ন ৬-tuple সংজ্ঞাগুলো পরে বইগুলোতে স্থির হয়েছে; মূল প্রবন্ধগুলোর ভাষা আর লক্ষ্য কিছুটা আলাদা ছিল, তাই নাম দুটিকে “উৎসের সম্মান” হিসেবে দেখাই নিরাপদ।

Moore-এর প্রবন্ধটি বিশেষভাবে আকর্ষণীয়, কারণ তাঁর প্রশ্ন ছিল প্রায় দার্শনিক: একটি যন্ত্রকে “কালো বাক্স” হিসেবে পেলে, শুধু ইনপুট দিয়ে আর output দেখে তার ভেতরের অবস্থা সম্পর্কে কী জানা যায়? তিনি দেখান যে কিছু তথ্য কোনো পরীক্ষাতেই জানা যায় না, আর দুটি state আলাদা কি না তা নির্দিষ্ট দৈর্ঘ্যের পরীক্ষায় ধরা যায়। এই ধারণা পরে state minimization (পর্ব ১৯), hardware-এর fault testing আর আধুনিক model learning-এর ভিত্তি হয়েছে।

এই ইতিহাস থেকে একটি শিক্ষা: একই গাণিতিক বস্তু প্রকৌশলের প্রশ্ন (circuit কীভাবে বানাব) আর বিজ্ঞানের প্রশ্ন (বাইরে থেকে কী জানা যায়) দুই দিক থেকেই এসেছে, আর দুই ধারাই আজও সক্রিয়।

মূল উপলব্ধি: Mealy আর Moore machine ১৯৫০-এর দশকের sequential circuit নকশা আর “কালো বাক্স পরীক্ষা”-র প্রশ্ন থেকে এসেছে; আজকের পরিচ্ছন্ন সংজ্ঞা পরে পাঠ্যবইয়ে স্থির হয়েছে।

প্র ০২দুটি মডেল গাণিতিকভাবে সমতুল্য। তাহলে hardware নকশায় প্রকৌশলীরা কখন Moore আর কখন Mealy বাছেন?

গাণিতিক সমতা বলে, একটি দিয়ে যা করা যায় অন্যটি দিয়েও তা করা যায়, প্রথম output-এর শর্ত মেনে। কিন্তু circuit-এ তিনটি জিনিস আলাদা: সময়, স্থিরতা আর আকার।

সময়ের দিক থেকে Mealy এগিয়ে। এর output state আর ইনপুট থেকে সরাসরি logic দিয়ে আসে, তাই একই clock cycle-এ সাড়া দেয়। Moore-এর output state register-এর পরে আসে, তাই ইনপুটের সাড়া এক cycle পরে দেখা যায়। একটি bus protocol-এ যদি “অনুরোধ পেলেই এই cycle-এ স্বীকার করো” নিয়ম থাকে, তবে Mealy-ই স্বাভাবিক।

স্থিরতার দিক থেকে Moore এগিয়ে। Mealy-র output ইনপুটের সঙ্গে সরাসরি যুক্ত, তাই ইনপুটে ছোট ঝাঁকুনি (glitch) বা অসম পথে আসা সংকেত output-এও ঝাঁকুনি আনতে পারে, আর এই output যদি অন্য কোনো যন্ত্রের ইনপুট হয়, তবে ভুল ছড়িয়ে পড়ে। তাছাড়া ইনপুট থেকে output পর্যন্ত একটি লম্বা combinational পথ তৈরি হয়, যা দুটি যন্ত্র জুড়লে clock-এর গতি সীমিত করতে পারে। Moore-এর output শুধু register থেকে, তাই একটি পুরো cycle স্থির থাকে। অনেক নকশা-নির্দেশিকা তাই module-এর সীমানায় “registered output” রাখার পরামর্শ দেয়।

আকারের দিক থেকে Mealy সাধারণত ছোট: উপপাদ্য ৪.৩ অনুযায়ী Moore-এ state বাড়তে পারে, যেমন 101 detector-এ ৩ থেকে ৪, serial adder-এ ২ থেকে ৪। বেশি state মানে কখনো বেশি flip-flop আর বড় next-state logic. বাস্তবে প্রকৌশলীরা প্রায়ই মিশ্র পথ নেন: ভেতরে Mealy ধাঁচের দ্রুত logic, আর বাইরে যাওয়ার আগে output-কে একটি register-এ ধরে রাখা, যা কার্যত Moore আচরণ দেয়। কম্পিউটার আর্কিটেকচার কোর্সের FSM পর্বে এই সিদ্ধান্তগুলো circuit স্তরে দেখানো আছে।

মূল উপলব্ধি: Mealy দ্রুত সাড়া দেয় আর কম state চায়; Moore এক cycle দেরিতে কিন্তু স্থির output দেয়। গাণিতিক সমতা সত্ত্বেও বাছাই হয় সময়, স্থিরতা আর আকারের আপসে।

প্র ০৩Finite-state transducer কম্পিউটার ভাষা-প্রক্রিয়ায় কীভাবে কাজে লাগে, আর এর সীমা কোথায়?

একটি শব্দ ভাবুন, যেমন “বইগুলোতে”। একটি ভাষা-প্রক্রিয়ার প্রোগ্রাম জানতে চায় এর মূল শব্দ “বই”, তারপর বহুবচন “গুলো”, তারপর বিভক্তি “তে”। এই ভাঙন বাঁ থেকে ডানে অক্ষর পড়তে পড়তে করা যায়, আর প্রতিটি ধাপে কী লিখতে হবে তা নির্ভর করে এ পর্যন্ত কী পড়া হয়েছে তার একটি সসীম সারাংশের ওপর। এটি একটি transducer-এর কাজ: ইনপুট শব্দ, output বিশ্লেষণ। এখানে বলা দরকার, বাংলার জন্য নির্দিষ্ট কোনো বাস্তব ব্যবস্থার দাবি আমরা করছি না; এটি ধারণা বোঝানোর একটি উদাহরণ।

গবেষণার ইতিহাসে ১৯৭০ থেকে ১৯৯০-এর দশকে কয়েকটি গুরুত্বপূর্ণ ফল আসে। C. Douglas Johnson ১৯৭২ সালে দেখান যে ধ্বনিতত্ত্বের অনেক rewrite নিয়ম, একটি নির্দিষ্ট শর্তে, আসলে regular relation; Kimmo Koskenniemi ১৯৮৩ সালে “two-level morphology” প্রস্তাব করেন; আর Ronald Kaplan ও Martin Kay ১৯৯৪ সালের প্রবন্ধে এই নিয়মগুলোকে transducer-এ রূপান্তরের পদ্ধতি বিস্তারিত দেন বলে জানা যায়। Speech recognition-এ Mehryar Mohri আর সহকর্মীরা weighted transducer দিয়ে উচ্চারণের মডেল, শব্দভান্ডার আর ভাষা-মডেলকে একটি যন্ত্রে জুড়ে দেওয়ার পদ্ধতি জনপ্রিয় করেন।

সীমাগুলো এই কোর্সের মূল প্রশ্নের সঙ্গে যুক্ত। Transducer-এর স্মৃতি সসীম, তাই এটি nested গঠন, যেমন অসীম গভীরতার বন্ধনী বা বাক্যের ভেতরে বাক্য, পুরোপুরি ধরতে পারে না; এর জন্য context-free grammar লাগে (পর্ব ২৫)। আর §৫-এ দেখেছেন, এমন সরল একটি function, serial গুণ, কোনো সসীম transducer করতে পারে না। তাছাড়া nondeterministic transducer-এর সমতা পরীক্ষা সাধারণভাবে undecidable, তাই দুটি বড় নিয়ম-সংকলন “একই কাজ করে কি না” স্বয়ংক্রিয়ভাবে সবসময় বলা যায় না। আধুনিক neural ভাষা-মডেল অনেক কাজ দখল করলেও, ছোট, দ্রুত আর ব্যাখ্যাযোগ্য ধাপে, যেমন text normalization-এ, transducer এখনো ব্যবহৃত হয় বলে জানা যায়।

মূল উপলব্ধি: Transducer ভাষার স্থানীয়, বাঁ-থেকে-ডানের রূপান্তর দ্রুত আর ব্যাখ্যাযোগ্যভাবে করে, কিন্তু সসীম স্মৃতির কারণে nested গঠন আর গুণের মতো কাজে আটকে যায়।

প্র ০৪যোগ দুই state-এ হয়, গুণ কোনো সসীম যন্ত্রে হয় না। একটি সসীম transducer ঠিক কোন ধরনের function হিসাব করতে পারে?

প্রথম শর্তটি সময়ের: Mealy machine-এর i-তম output নির্ভর করে শুধু প্রথম iটি ইনপুটের ওপর। একে বলে causal বা “ভবিষ্যৎ না দেখা”। তাই output-এর দৈর্ঘ্য ইনপুটের সমান, আর w-এর output সবসময় wx-এর output-এর prefix. যে function এই শর্ত ভাঙে, যেমন ইনপুট উল্টে লেখা, তা কোনো Mealy machine পারে না: প্রথম output চিহ্নটি ইনপুটের শেষ চিহ্ন, যা তখনো পড়াই হয়নি।

দ্বিতীয় শর্তটি স্মৃতির: ভবিষ্যৎ আচরণের “রকম” সসীম হতে হবে। §৫-এর গুণের প্রমাণ ঠিক এটিই দেখায়: n জোড় পড়ার পর 2n−1 রকম ভবিষ্যৎ থাকলে অন্তত ততগুলো state লাগে। যোগে ভবিষ্যৎ নির্ভর করে শুধু carry-র ওপর, তাই দুই রকম। আরেকটি সুন্দর উদাহরণ ৩ দিয়ে ভাগ: binary সংখ্যা বড় বিট থেকে পড়লে ভাগফলের প্রতিটি বিট তখনই লেখা যায়, আর মনে রাখতে হয় শুধু ভাগশেষ 0, 1 বা 2, অর্থাৎ তিনটি state. অথচ একই সংখ্যাকে ৩ দিয়ে গুণ করা ছোট বিট থেকে পড়লে সহজ (carry 0, 1 বা 2), বড় বিট থেকে পড়লে কঠিন, কারণ তখন output-এর প্রথম বিট নির্ভর করে পরে আসা carry-র ওপর। পড়ার দিক এখানে গুরুত্বপূর্ণ।

তত্ত্বে এই শ্রেণির function-কে বলা হয় sequential function, আর Mealy machine-এর চেয়ে একটু সাধারণ “subsequential transducer” শেষে একটি বাড়তি string লিখতে পারে। এ নিয়ে বিস্তারিত গবেষণা আছে, যেমন কোন function এমন যন্ত্রে হয় তার একটি যন্ত্র-নিরপেক্ষ বৈশিষ্ট্য (bounded variation ধরনের শর্ত), যা Christian Choffrut-এর কাজের সঙ্গে যুক্ত বলে জানা যায়। মূল ধারণা Myhill–Nerode-এর মতো: সমতুল্য prefix-এর শ্রেণি সসীম কি না।

প্রোগ্রামিংয়ে এর সমতুল্য হলো streaming বা online algorithm: ডেটা একবার পড়ে, স্থির স্মৃতিতে, সঙ্গে সঙ্গে output দেওয়া। Checksum, parity, running total-এর mod: এগুলো সবই ছোট transducer.

মূল উপলব্ধি: সসীম transducer সেই function পারে, যার output ভবিষ্যৎ ইনপুট দেখে না আর যার “ভবিষ্যৎ আচরণের রকম” সসীম; যোগ ও ৩ দিয়ে ভাগ এই শর্ত মানে, গুণ ও উল্টে লেখা মানে না।

প্র ০৫একটি software-এর ভেতরের state machine জানা নেই। বাইরে থেকে ইনপুট দিয়ে আর output দেখে কি সেই Mealy machine উদ্ধার করা যায়?

এটি Moore-এর ১৯৫৬ সালের “কালো বাক্স” প্রশ্নেরই আধুনিক রূপ, আর এর দুটি ধারা আছে: testing আর learning.

Testing-এর দিকে প্রশ্নটি এমন: নকশার Mealy machine জানা আছে, আর একটি implementation সত্যিই সেটি মেনে চলে কি না, তা কয়েকটি ইনপুট-ক্রম দিয়ে যাচাই করা যায় কি? Tsun Chow ১৯৭৮ সালে finite-state machine থেকে test sequence বানানোর একটি পদ্ধতি প্রকাশ করেন, যা পরে W-method নামে পরিচিত হয়। মূল ধারণা: প্রতিটি state-এ পৌঁছানোর একটি ইনপুট, প্রতিটি transition একবার চালানো, তারপর এমন কয়েকটি ক্রম যা state-গুলোকে আলাদা করে চেনায়। শর্ত আছে: implementation-এর state সংখ্যার একটি ওপরের সীমা জানা থাকতে হয়, নইলে কোনো সসীম পরীক্ষাই নিশ্চয়তা দেয় না। এই কোর্সের ভাষায়, এটি দুটি যন্ত্রের সমতার পরীক্ষা, যেখানে একটির ভেতর দেখা যায় না।

Learning-এর দিকে Dana Angluin ১৯৮৭ সালে L* algorithm দেন, যা একজন “শিক্ষক”-এর কাছে দুই ধরনের প্রশ্ন করে একটি অজানা regular language-এর minimal DFA শেখে: “এই string কি language-এ?” আর “আমার অনুমান কি ঠিক, না হলে একটি পাল্টা-উদাহরণ দিন”। পরে এই পদ্ধতি Mealy machine-এর জন্য মানিয়ে নেওয়া হয়, যেখানে প্রশ্ন হলো “এই ইনপুট-ক্রমে output কী?”। বাস্তবে দ্বিতীয় ধরনের প্রশ্নের উত্তর কেউ দেয় না, তাই সেটি অনেক পরীক্ষা চালিয়ে আনুমানিকভাবে করা হয়। গবেষকেরা এভাবে network protocol-এর implementation থেকে state machine শিখে নকশার সঙ্গে না-মেলা অপ্রত্যাশিত transition খুঁজে পেয়েছেন বলে কয়েকটি প্রকাশিত গবেষণায় জানা যায়; নিরাপত্তার দিক থেকে এগুলো মূল্যবান, কারণ অবৈধ transition প্রায়ই দুর্বলতার জায়গা। এ ধরনের পরীক্ষা শুধু নিজের বা অনুমতিপ্রাপ্ত সিস্টেমে করা উচিত।

মূল উপলব্ধি: বাইরে থেকে একটি Mealy machine যাচাই বা শেখা সম্ভব, কিন্তু state সংখ্যার সীমার মতো শর্ত লাগে; W-method আর L* এই প্রশ্নের দুটি ক্লাসিক উত্তর।

অনুশীলন

আগে খাতায় করুন, তারপর উত্তর খুলে মেলান।

  1. নকশা: একটি Moore machine নকশা করুন, যা বড় বিট থেকে একটি binary সংখ্যা পড়ে আর প্রতিটি prefix-এর পরে সেই prefix-এর মান mod 3 লেখে (Δ = {0, 1, 2})। Transition table আর প্রতিটি state-এর অর্থ লিখুন, তারপর 1101-এ output বের করুন।

    State r ∈ {0, 1, 2} মানে “এ পর্যন্ত পড়া prefix-এর মান mod 3 = r”; start 0 (ফাঁকা prefix-এর মান 0), ω(r) = r. Prefix v-এর পরে বিট a এলে নতুন মান 2v + a, তাই δ(r, a) = (2r + a) mod 3.

    state01ω
    → 0010
    1201
    2122

    1101-এ run 0 → 1 → 0 → 0 → 1, output 01001: prefix ε, 1, 11, 110, 1101-এর মান 0, 1, 3, 6, 13, আর mod 3-এ 0, 1, 0, 0, 1. সঠিকতা: invariant “state = prefix-এর মান mod 3”, |w|-এর ওপর induction, কারণ (2v + a) mod 3 = (2(v mod 3) + a) mod 3. দৈর্ঘ্য 12 পর্যন্ত সব string-এ scratch-এ পূর্ণ গণনায় মেলানো।

  2. ভুল খুঁজুন: একজন লিখেছেন, “প্রতিটি Mealy machine-এর একটি সমতুল্য Moore machine আছে একই সংখ্যক state-এ: প্রতিটি state-এর output হবে তাতে ঢোকা তীরের output.” ভুলটি কোথায়? একটি Mealy machine দিন, যার সমতুল্য প্রতিটি Moore machine-এ বেশি state লাগে, আর প্রমাণ করুন।

    ভুল: একটি state-এ ঢোকা বিভিন্ন তীরে বিভিন্ন output থাকতে পারে; তখন “ঢোকা তীরের output” একটি মান নয়, তাই ω সংজ্ঞায়িতই হয় না। 101 detector-এ S1-এ 1/0 আর 1/1 দুটি তীর ঢোকে।

    পাল্টা-উদাহরণ: Copy machine, Σ = Δ = {0, 1}, এক state s, ω(s, a) = a. দাবি: সমতুল্য প্রতিটি Moore machine-এ অন্তত ২টি state.

    1. ধরুন এক state p-এর Moore machine M′ সমতুল্য। এক state বলে সব run p-তেই থাকে। — |Q| = 1
    2. তাই TM′(0) = ω(p)ω(p) আর TM′(1) = ω(p)ω(p). — Moore-এর output-এর সংজ্ঞা
    3. সমতা চায় TM′(0) = ω(p) · 0 আর TM′(1) = ω(p) · 1, অর্থাৎ ω(p) = 0 আর ω(p) = 1 একসঙ্গে, বিরোধ। ∎ — সংজ্ঞা ৪.১

    উপপাদ্য ৪.৩-এর construction এখানে ২টি state দেয়, (s, 0) আর (s, 1), তাই ২-ই সবচেয়ে কম।

  3. আউটপুট অনুমান: §৫-এর serial adder (start C0) 11 + 5 হিসাব করছে, ৫টি বিট-জোড়ে, LSB আগে: (1,1), (1,0), (0,1), (1,0), (0,0). প্রতিটি ধাপের state আর output লিখুন, আর output-কে সংখ্যা হিসেবে পড়ুন। পঞ্চম জোড়টি বাদ দিলে কী হতো?
    pair  (1,1) (1,0) (0,1) (1,0) (0,0)
    state C0 -> C1 -> C1 -> C1 -> C1 -> C0
    out     0     0     0     0     1

    প্রথম জোড়ে 1 + 1 = 2, output 0, carry 1; তারপর তিনবার 1 + 0 + 1 = 2 বা 0 + 1 + 1 = 2, প্রতিবার output 0, carry 1; শেষ জোড়ে 0 + 0 + 1 = 1, output 1, carry 0. Output LSB আগে 00001, উল্টে 10000 = 16 = 11 + 5. পঞ্চম জোড় না দিলে output 0000 আর শেষ carry 1 যন্ত্রের ভেতরে থেকে যেত, উত্তর ভুলভাবে 0 পড়া হতো। (scratch-এ চালিয়ে মেলানো।)

  4. রূপান্তর: Overlap ছাড়া 101 detector-এর Mealy machine: S0: 0/0 → S0, 1/0 → S1; S1: 0/0 → S2, 1/0 → S1; S2: 0/0 → S0, 1/1 → S0. b0 = 0 নিয়ে উপপাদ্য ৪.৩-এর পদ্ধতিতে Moore machine বানান, শুধু পৌঁছানো state রেখে। কয়টি state হয়?
    state01ω′
    → (S0, 0)(S0, 0)(S1, 0)0
    (S1, 0)(S2, 0)(S1, 0)0
    (S2, 0)(S0, 0)(S0, 1)0
    (S0, 1)(S0, 0)(S1, 0)1

    ৪টি state. এবার ভাগ হয়েছে S0, কারণ S0-তে 0/0 আর 1/1 দুই ধরনের তীর ঢোকে। (S0, 1) “এইমাত্র মিল হলো, আর সব ভুলে গেছি” অবস্থা: তার তীর (S0, 0)-এর মতোই। (S1, 1) আর (S2, 1)-এ পৌঁছানো যায় না। §৪-এর রূপান্তর ব্লকে এই যন্ত্রেরই “no-overlap: 3 -> 4 states” লাইন।

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

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

ক্রমSerial binary adder দিয়ে দুটি সংখ্যা যোগের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. দুটি সংখ্যাকে সমান দৈর্ঘ্যের binary-তে লেখা, দরকারে বাঁয়ে 0 বসিয়ে
  2. Carry 0 অর্থাৎ start state C0 থেকে শুরু করা
  3. সবচেয়ে কম গুরুত্বের বিট-জোড় পড়ে sum বিট লেখা আর carry হালনাগাদ করা
  4. পরের বিট-জোড়গুলো একইভাবে, বড় বিটের দিকে এগিয়ে
  5. শেষে একটি বাড়তি (0, 0) জোড় দিয়ে শেষ carry-কে বিট হিসেবে লেখানো
  6. Output-কে উল্টো দিক থেকে পড়ে যোগফল লেখা

একটি Moore machine দৈর্ঘ্য n-এর একটি ইনপুট string পড়লে কয়টি output চিহ্ন লেখে?

  • n − 1
  • n
  • n + 1
  • 2n

Mealy machine M = (Q, Σ, Δ, δ, ω, q0)-এর output function ω কোন ধরনের?

  • ω: Q → Δ
  • ω: Q × Σ → Δ
  • ω: Q × Σ → Q
  • ω: Q × Σ → P(Δ)

একটি Mealy machine-এর 3টি state আর output alphabet-এ 2টি চিহ্ন। (q, b) জোড় দিয়ে বানানো সমতুল্য Moore machine-এ সর্বোচ্চ কয়টি state লাগতে পারে?

  • 3
  • 5
  • 8
  • 6

Mealy machine: state S0, S1, S2, start S0. S0: 0/0 → S0, 1/0 → S1; S1: 0/0 → S2, 1/0 → S1; S2: 0/0 → S0, 1/1 → S1. ইনপুট 10101-এ output কী?

  • 00101
  • 000101
  • 00100
  • 01010

দুটি binary সংখ্যার বিট-জোড় কম গুরুত্বের বিট থেকে পড়ে ফলের বিট লেখা হবে। কোন কাজটি কোনো সসীম Mealy machine করতে পারে না?

  • দুটি সংখ্যার যোগফল
  • বিট-বিট XOR
  • দুটি সংখ্যার গুণফল
  • প্রতিটি prefix-এ প্রথম সংখ্যা দ্বিতীয়টির চেয়ে বড় কি না

Moore machine M = (Q, Σ, Δ, δ, ω, q0) থেকে একই state-এর সমতুল্য Mealy machine বানাতে নতুন output function ω′(q, a) কী হবে?

  • ω(q)
  • ω(δ(q, a))
  • a
  • ω(q0)

শব্দকোষ

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

মনে রাখুন

  1. দুই মডেল: Moore (Q, Σ, Δ, δ, ω, q0), ω: Q → Δ, n + 1টি output; Mealy-তে ω: Q × Σ → Δ, nটি output.
  2. সমতা: TMoore(w) = ω(q0) · TMealy(w); প্রথম চিহ্নটি ইনপুটের সাড়া নয়, তাই বাদ দিয়ে তুলনা।
  3. রূপান্তর: Moore → Mealy: ω′(q, a) = ω(δ(q, a)), একই state. Mealy → Moore: state (q, b), বড়জোর |Q| · |Δ|টি, শুধু পৌঁছানো জোড়।
  4. Detector: 101 overlap সহ Mealy ৩, Moore ৪ state; overlap ছাড়া শুধু মিলের পরের তীরের গন্তব্য বদলায়।
  5. Adder আর সীমা: Serial adder-এর state শুধু carry, শেষে একটি বাড়তি (0, 0) জোড়; serial গুণ কোনো সসীম যন্ত্রে অসম্ভব।

পরের পর্বে: পর্ব ১৩ “Regular expression — formal definition আর বীজগণিত”: মডিউল ৩ শুরু। যন্ত্রের বদলে একটি সূত্র দিয়ে regular language লেখা, union, concatenation আর star-এর নিয়ম, আর regex-এর বীজগণিতের অভেদ।

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

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