সসীম অটোমেটন
সসীম অটোমেটন (ইংরেজিতে finite state machine বা finite automaton) হলো একটি আদিম কম্পিউটারের গণনার মডেল। এটি কয়েকটি স্টেট (state) ও কয়েকটি ট্রানজিশন (transition) নিয়ে গঠিত, আর প্রদত্ত স্ট্রিং গ্রহণ (accept) বা বর্জন (reject) করতে পারে।
উদাহরণ
অনানুষ্ঠানিকভাবে সসীম অটোমেটনকে আমরা স্টেট চিত্র দিয়ে বর্ণনা করব:
অটোমেটন স্টেট দিয়ে গঠিত। চিত্রে এগুলো তিনটি গোল স্টেট q0, q1 ও q2। এই স্টেটগুলোর মধ্যে আছে ট্রানজিশন, অর্থাৎ তীরগুলো। অটোমেটনে একটি প্রারম্ভিক স্টেটও থাকতে হয়, এখানে সেটি q0। প্রারম্ভিক স্টেটকে প্রায়ই এমন একটি তীর দিয়ে দেখানো হয়, যা এর দিকে আসে কিন্তু কোনো স্টেট থেকে বের হয় না। এ ছাড়া অটোমেটনে সাধারণত চূড়ান্ত স্টেট থাকে, তা আমরা দুই রেখা দিয়ে আঁকি। চিত্রে এটি স্টেট q2।
এভাবে গঠিত অটোমেটন কিছু স্ট্রিং গ্রহণ করে। আমরা অটোমেটনে স্ট্রিং দিই, অটোমেটন সেগুলো গ্রহণ করার চেষ্টা করে। গ্রহণ করলে অটোমেটনের উত্তর “হ্যাঁ”, গ্রহণ না করলে উত্তর “না”। আমাদের অটোমেটন “a, b, c” বর্ণ দিয়ে গঠিত স্ট্রিং গ্রহণ করার চেষ্টা করে, তাই স্ট্রিং “abbc” দিয়ে চেষ্টা করে দেখা যাক।
আমরা শুরু করি প্রারম্ভিক স্টেট q0 থেকে, ইনপুটে আছে স্ট্রিং “abbc”। এরপর তীর অনুসরণ করব।
স্ট্রিংটি আমরা সাধারণ নিয়মে বাম থেকে ডানে পড়ি, অর্থাৎ প্রথমে নিই প্রতীক “a”। ইনপুট “a” এর তীর যায় স্টেট q1 এ, তাই আমরা সেখানে যাই এবং স্ট্রিং থেকে প্রতীক “a” মুছে ফেলি। ইনপুটে থাকে স্ট্রিং “bbc”:
ইনপুট “b” এর তীর আবার নোড q1 এ ফিরে আসে। আবার প্রথম বর্ণটি মুছে ফেলি, ইনপুটে থাকে স্ট্রিং “bc”। আবারও আমরা স্টেট q1 এ থাকি। শেষে ইনপুটে থাকে স্ট্রিং “c”। স্টেট q1 থেকে ইনপুট “c” এর তীর আমাদের পাঠায় স্টেট q2 এ।
ইনপুট স্ট্রিংয়ের সব বর্ণ শেষ, আর আমরা আছি স্টেট q2 এ, যা একটি চূড়ান্ত স্টেট। তাই এই সসীম অটোমেটন স্ট্রিং “abbc” গ্রহণ করে।
শেষে আমরা গ্রহণকারী স্টেটে না থাকলে অটোমেটন স্ট্রিংটি গ্রহণ করত না। কোনো স্টেট থেকে যাওয়ার জায়গা না থাকলেও অটোমেটন স্ট্রিংটি গ্রহণ করত না। যেমন, ইনপুট “ab” এর জন্য আমরা পৌঁছাতাম স্টেট q1 এ এবং সেখানেই থেমে যেতাম, তাই অটোমেটন এমন স্ট্রিং গ্রহণ করে না। স্ট্রিং “aabbc” পরীক্ষা করলেও কপাল মন্দ, কারণ স্টেট q1 থেকে বর্ণ “a” এর কোনো তীর নেই।
সুতরাং সসীম অটোমেটনের কাজ হলো কোনো একটি স্ট্রিংয়ের সেট শনাক্ত করা। বাস্তবে অটোমেটন দিয়ে আমরা যেমন যাচাই করতে পারি, প্রদত্ত ইনপুট স্ট্রিংটি বৈধ ইমেইল ঠিকানা কি না।
সসীম অটোমেটনের সংজ্ঞা
অটোমেটন নিয়ে আরও ভালোভাবে কাজ করতে হলে সসীম অটোমেটন সম্পর্কে আগের এই সহজাত ধারণাকে আনুষ্ঠানিক রূপ দিতে হবে।
আমরা বলি, (নির্ধারণমূলক) সসীম অটোমেটন হলো একটি পঞ্চক ⟨Q, Σ, δ, q0, F⟩, যেখানে
- Q হলো স্টেটগুলোর একটি সসীম সেট,
- Σ (বড় হাতের সিগমা) হলো বর্ণমালা (প্রতীক বা বর্ণের একটি সসীম সেট),
- δ: Q × Σ ⟶ Q হলো ট্রানজিশন ফাংশন,
- q0 ∈ Q হলো প্রারম্ভিক স্টেট,
- F ⊆ Q হলো চূড়ান্ত (গ্রহণকারী) স্টেটগুলোর সেট।
আগের অটোমেটনে ফিরে গেলে,
বলতে পারি, স্টেটের সেট Q এ তিনটি স্টেট আছে: Q = {q0, q1, q2}। বর্ণমালা Σ এ আছে সেইসব বর্ণ, যা দিয়ে আমরা স্ট্রিং বানাতে পারি, আর অটোমেটন সেই স্ট্রিং গ্রহণ বা বর্জন করবে। এখানে সম্ভবত বর্ণমালাটি Σ= {a, b, c}, তবে এটি এর যেকোনো অধিসেটও হতে পারে। প্রারম্ভিক স্টেট q0 হলো স্টেট q0, এতে কোনো পরিবর্তন নেই। এই অটোমেটনে চূড়ান্ত স্টেটের সেটে শুধু একটি স্টেট আছে: F = {q2}।
ট্রানজিশন ফাংশন বলতে বোঝায় বর্ণ লেখা সেই তিনটি তীর। δ: Q × Σ ⟶ Q লেখাটি যদি বিভ্রান্ত করে, তবে এর অর্থ শুধু এই যে δ একটি ফাংশন (আরও ভালো বললে চিত্রণ), যা দুইটি প্যারামিটার নেয়: Q থেকে একটি স্টেট এবং Σ থেকে একটি বর্ণ। ফাংশনটি কল করলে এটি একটি নতুন স্টেট দেয়। আমাদের ট্রানজিশন ফাংশনকে সারণি দিয়ে এভাবে সংজ্ঞায়িত করা যায়:
তাই δ(q1, c) কল করলে আমরা তৃতীয় সারিটি প্রয়োগ করি, আর ফাংশনটি উত্তর দেয় স্টেট q2, চিত্রের মতোই। আমরা স্টেট q1 এ থাকলে এবং ইনপুটে বর্ণ “c” থাকলে পৌঁছাই স্টেট q2 এ। অটোমেটন কোনো স্ট্রিং গ্রহণ করে বলতে কী বোঝায়, তা আনুষ্ঠানিকভাবে সংজ্ঞায়িত করার আগে আমরা এই ধারণার সহজাত বোঝাপড়া কাজে লাগিয়ে আরও কয়েকটি উদাহরণ দেখব।
আরও উদাহরণ
-
এমন একটি অটোমেটন তৈরি কর, যা দ্বিমিক বর্ণমালা Σ= {0, 1} এর উপর কাজ করে এবং শুধু এক দিয়ে শেষ হওয়া স্ট্রিং গ্রহণ করে। যেমন, এটি গ্রহণ করে 1, 01, 000001, 0101011 স্ট্রিংগুলো।
আমাদের অটোমেটনের দুইটি স্টেট: প্রারম্ভিক q0 ও চূড়ান্ত q1। ইনপুটে অঙ্ক 1 থাকলেই আমরা চূড়ান্ত স্টেট q1 এ যাই এবং সেখানে থাকি। উল্টো দিকে, ইনপুটে অঙ্ক 0 থাকলে আমরা অচূড়ান্ত স্টেট q0 এ যাই এবং সেখানেও থাকি।
-
দ্বিমিক বর্ণমালার উপর এমন একটি অটোমেটন গঠন কর, যা শুধু সেইসব স্ট্রিং গ্রহণ করে, যাদের প্রথম বর্ণ শেষ বর্ণের সমান নয়।
প্রথম ধাপেই অটোমেটনটি দুইটি “উপ-অটোমেটনে” ভাগ হয়ে যায়। স্ট্রিং শূন্য দিয়ে শুরু হলে অটোমেটন বাম অংশে ঢোকে এবং সেখানেই থাকে, এক দিয়ে শুরু হলে চলে যায় ডান অংশে। এরপর সবকিছু চেনা: বাম অংশে থাকা অবস্থায় ইনপুটে 1 থাকলে আমরা চূড়ান্ত স্টেটে যাই এবং সেখানেই থাকি। ইনপুটে 0 থাকলে যাই স্টেট q1 এ, যা চূড়ান্ত নয়।
আগের অটোমেটনগুলোর বিপরীতে এই অটোমেটনে একাধিক চূড়ান্ত স্টেট আছে: F = {q3, q4}।
-
দ্বিমিক বর্ণমালার উপর এমন একটি অটোমেটন গঠন কর, যা শুধু সেইসব স্ট্রিং গ্রহণ করে, যাতে পরপর দুইটি শূন্য নেই।
এই অটোমেটনটি দুইটি কারণে আকর্ষণীয়। প্রথমত, এটি ফাঁকা স্ট্রিং গ্রহণ করে। অটোমেটনে ফাঁকা স্ট্রিং দিলে অটোমেটন তা গ্রহণ করে, যদি প্রারম্ভিক স্টেটটি একই সঙ্গে চূড়ান্ত স্টেটও হয়, আর এই অটোমেটনে তাই হয়েছে। ফাঁকা স্ট্রিংয়ে যেহেতু পরপর দুইটি শূন্য নেই, তাই এটিই সঠিক। দ্বিতীয়ত, এই অটোমেটনের সব স্টেটই চূড়ান্ত। অটোমেটন কোনো স্ট্রিং গ্রহণ করবে না একমাত্র তখনই, যখন কোনো স্টেট থেকে কোনো ট্রানজিশন নেই। তা ঘটে স্টেট q1 এ, যেখানে 0 এর ট্রানজিশন নেই, কারণ তা থাকলে স্ট্রিংয়ে পরপর দুইটি শূন্য থাকত।
-
বর্ণমালা {-,+,.,0,1,…,9} এর উপর এমন একটি অটোমেটন গঠন কর, যা শুধু সংখ্যা প্রকাশ করে এমন স্ট্রিং গ্রহণ করে। অর্থাৎ হয় পূর্ণ সংখ্যা, যেমন 2, 548, 98263, নয়তো দশমিক সংখ্যা, যেমন 5584.48, 3.14, আর দুই ধরনেরই বিয়োগচিহ্নসহ ঋণাত্মক রূপ -2, -548, -3.14, এবং স্পষ্টভাবে লেখা যোগচিহ্নসহ রূপ, অর্থাৎ +2, +548, +3.14। সেই সঙ্গে সংখ্যা 0.123 কে শুধু .123 (শুরুর শূন্য ছাড়া) হিসেবেও লিখতে পারতে হবে, দুই চিহ্নসহও। দশটি অঙ্কের জন্য দশটি ট্রানজিশন না লিখে আমরা একটি সহায়ক চিহ্ন N ব্যবহার করব।
-
দ্বিমিক বর্ণমালার উপর এমন একটি অটোমেটন গঠন কর, যা শুধু 0n1n আকারের স্ট্রিং গ্রহণ করে। অর্থাৎ স্ট্রিংয়ের শুরুতে কিছু সংখ্যক শূন্য থাকে, তারপর থাকে সমান সংখ্যক এক। এমন স্ট্রিংয়ের উদাহরণ 0011, 00001111, 01।
এমন অটোমেটন গঠন করা যায় না, কারণ শূন্যের সংখ্যা কোথাও “মনে রাখার” উপায় আমাদের নেই। দ্বিতীয় উদাহরণের মতো কয়েকটি “উপ-অটোমেটন” বানাতে হতো, কিন্তু সেই “উপ-অটোমেটন” লাগত অসীম সংখ্যক, n এর প্রত্যেক মানের জন্য একটি করে।
অটোমেটনের গণনার আনুষ্ঠানিক রূপ
সসীম অটোমেটনকে আমরা আনুষ্ঠানিকভাবে সংজ্ঞায়িত করেছি। এখন সংজ্ঞায়িত করতে হবে, এমন অটোমেটন আসলে কী করে, অর্থাৎ অটোমেটনের গণনা।
অটোমেটনের কনফিগারেশন: জোড় ⟨q, w⟩ ∈ Q × Σ∗ কে আমরা অটোমেটনের কনফিগারেশন (configuration) বলি, যেখানে q হলো অটোমেটন এই মুহূর্তে যে স্টেটে আছে, আর w হলো স্ট্রিংয়ের এখনো না পড়া অংশ। Σ∗ হলো বর্ণমালা Σ এর ক্লোজার, অর্থাৎ Σ এর বর্ণ দিয়ে বানানো যায় এমন সব স্ট্রিংয়ের সেট। ক্লোজারে ফাঁকা স্ট্রিংও আছে, যাকে লিখি ε।
অটোমেটন ⟨Q, Σ, δ, q0, F⟩ দিয়ে স্ট্রিং w গ্রহণ করার চেষ্টা করলে অটোমেটন থাকে প্রারম্ভিক কনফিগারেশন ⟨q0, w⟩ এ। আবার অটোমেটনটিতে ফিরে যাই
এবং স্ট্রিং w = abbc গ্রহণ করতে চাই। তাহলে প্রারম্ভিক কনফিগারেশন হবে ⟨q0, abbc⟩।
গণনার ধাপকে আমরা (Q × Σ∗) × (Q × Σ∗) এর উপর একটি অন্বয় ↦ হিসেবে সংজ্ঞায়িত করি, অর্থাৎ অটোমেটনের কনফিগারেশনগুলোর মধ্যে অন্বয়। ধরি w = w0w1… wn হলো স্ট্রিং w এর এখনো না পড়া অংশ। তাহলে আমরা বলি, জোড় ⟨q1, w0w1… wn⟩ ও ⟨q2, w1… wn⟩ অন্বয় ↦ এ আছে, এবং লিখি
যদি এবং কেবল যদি δ(q1, w0) = q2। আমাদের উদাহরণে ফিরে গেলে প্রারম্ভিক কনফিগারেশন ⟨q0, abbc⟩। চিত্র থেকে দেখি, ইনপুট “a” এর জন্য আমরা স্টেট q1 এ যেতে পারি। তাই লিখতে পারি
কারণ δ(q0, a) = q1। এভাবে আমরা গণনার একটি ধাপ সম্পন্ন করলাম: দেখলাম, প্রদত্ত ইনপুটের (= স্ট্রিংয়ের না পড়া অংশের প্রথম বর্ণ) জন্য কোন স্টেটে যাওয়া উচিত, সেখানে গেলাম, এবং না পড়া অংশ থেকে প্রথম বর্ণটি মুছে ফেললাম। এতে পেলাম একটি নতুন কনফিগারেশন।
গণনার ধাপ অন্বয়ের স্বসম ও সংক্রমণশীল ক্লোজারকে লিখি ↦ ∗। তাই K1 ↦ ∗ K2 লিখলে, যেখানে K1, K2 অটোমেটনের কনফিগারেশন, এর অর্থ হলো কনফিগারেশন K1 থেকে গণনার কয়েকটি ধাপে আমরা কনফিগারেশন K2 এ পৌঁছাতে পারি। অন্যভাবে বললে, কনফিগারেশনের এমন একটি সসীম অনুক্রম আছে, যেন:
যেমন, আমাদের অটোমেটনে ⟨q0, abbc⟩ ↦ ∗ ⟨q1,bc⟩, কারণ গণনার দুইটি ধাপের পর বাকি থাকে স্ট্রিং “bc” এবং আমরা থাকি স্টেট q1 এ। অর্থাৎ কনফিগারেশনের এই অনুক্রমটি আছে:
অটোমেটন স্ট্রিং w গ্রহণ করে যদি এবং কেবল যদি এমন qf ∈ F থাকে, যেন
এবং স্টেট q2 একটি চূড়ান্ত স্টেট, q2 ∈ F।
অটোমেটন দ্বারা গৃহীত ভাষা হলো অটোমেটন যত স্ট্রিং গ্রহণ করে, তাদের সবগুলোর সেট। অটোমেটন A এর ভাষাকে লিখব L(A)। তাহলে L(A) ⊆ Σ∗ এবং
রেগুলার ভাষা (regular language) হলো এমন ভাষা, যা কোনো একটি সসীম অটোমেটন গ্রহণ করে।
দুইটি সসীম অটোমেটন সমতুল্য, যদি দুইটিই একই ভাষা গ্রহণ করে। অর্থাৎ অটোমেটন A1 ও A2 সমতুল্য, যদি L(A1) = L(A2) হয়।
তথ্যসূত্র
সূচিপত্র: সসীম অটোমেটন, সম্পূর্ণ অটোমেটন, অনির্ধারণমূলক সসীম অটোমেটন, অনির্ধারণমূলক অটোমেটনের সিমুলেশন, NFA থেকে DFA তে রূপান্তর