✖

অনির্ধারণমূলক সসীম অটোমেটন

আগের অধ্যায়গুলোতে দেখানো সসীম অটোমেটন (সংক্ষেপে FA বা DFA) সবসময় নির্ধারণমূলক ছিল। এর অর্থ, প্রতিটি মুহূর্তে স্পষ্ট ছিল অটোমেটন কী করবে। এখন আমরা আরও সাধারণ একটি ধারণা দেখব: অনির্ধারণমূলক সসীম অটোমেটন (non-deterministic finite automaton, সংক্ষেপে NFA)। এতে এমন ট্রানজিশন থাকতে পারে, যেগুলো একই স্টেট থেকে বের হয় এবং একই প্রতীকের জন্য।

উদাহরণ

নিচের অটোমেটনের চিত্রটি দেখ:

এতে অদ্ভুত কী? নোড q0 থেকে প্রতীক 0 এর জন্য দুইটি প্রান্ত বের হয়েছে। তাই স্ট্রিং 001 গ্রহণ করার চেষ্টা করলে মনে হতে পারে, অটোমেটন জানবে না তাকে স্টেট q0 এ থাকতে হবে, নাকি q1 এ যাওয়ার ট্রানজিশন অনুসরণ করতে হবে। এমন অটোমেটন হবে অনির্ধারণমূলক।

এখানে নির্ধারণমূলকতার অর্থ হলো, প্রতিটি পরিস্থিতিতে স্পষ্ট থাকে অটোমেটন কী করবে, অস্পষ্টতার কোনো সুযোগ থাকে না। নির্ধারণমূলক অটোমেটনে প্রত্যেক স্টেট ও প্রত্যেক প্রতীকের জন্য শুধু একটি ট্রানজিশন থাকে। অনির্ধারণমূলকতা মানে অস্পষ্টতা: একটি স্টেট থেকে একই প্রতীকের জন্য হয়তো তিনটি ট্রানজিশন বের হতে পারে।

তাহলে অটোমেটন সিদ্ধান্ত নেয় কীভাবে? অনির্ধারণমূলক অটোমেটন সবসময় সেই ট্রানজিশনটি বেছে নেয় (কখনো আমরা বলি “অনুমান করে”), যা স্ট্রিংটি গ্রহণের দিকে নিয়ে যায়, যদি তা সম্ভব হয়।

অটোমেটনে স্ট্রিং 001 দিলে স্ট্রিংটি নিয়ে অটোমেটনের সামনে এই সম্ভাবনাগুলো থাকে:

q0→q0→q0→q0q0→q0→q1→q2

সঙ্গে সেইসব সম্ভাবনা, যেখানে অটোমেটন পুরো স্ট্রিং পড়ে না। প্রথমটিতে অটোমেটন সারাক্ষণ স্টেট q0 এ থেকেছে, যা সে অবশ্যই পারে, ট্রানজিশনের নিয়ম তা অনুমোদন করে। দ্বিতীয় শাখায় সে সাহস করে পরের স্টেটগুলোতে গেছে এবং শেষে পৌঁছেছে স্টেট q2 এ, যা চূড়ান্ত। এই শাখায় অটোমেটন স্ট্রিংটি গ্রহণ করত। অনির্ধারণমূলক অটোমেটন সবসময় আপনাআপনি সেই শাখা বেছে নেয়, যেখানে সে স্ট্রিংটি গ্রহণ করে, যদি এমন শাখা থাকে।

সে কীভাবে আপনাআপনি সেই “অনুকূল” শাখাটি বেছে নেয়? কল্পনা করতে পার, অনির্ধারণমূলক অটোমেটন সম্ভাব্য সব শাখা ঘুরে দেখে, আর এমন কোনো শাখা পেলে, যেখানে স্ট্রিংটি গৃহীত হয়, তখন স্ট্রিংটি গ্রহণ করে। সব শাখা সে ঘুরবে কীভাবে? সহজ কথায়, যখন সে এমন স্টেটে থাকে, যেখান থেকে বর্তমান প্রতীকের জন্য n টি প্রান্ত বের হয়েছে, তখন অটোমেটন নিজের n টি কপি বানায়, আর প্রত্যেক কপি ভিন্ন পথে যায়। এভাবে একে একে আমরা সব সম্ভাবনা ঘুরে দেখি।

অটোমেটনের গণনার বৃক্ষরূপ

আগের অটোমেটনটি সামান্য বদলে নিই:

অনির্ধারণমূলকতা রয়ে গেছে প্রথম স্টেটে। আগের অটোমেটন গ্রহণ করত 01 দিয়ে শেষ হওয়া সব স্ট্রিং। এই পরিবর্তিত অটোমেটন গ্রহণ করে সেইসব স্ট্রিং, যাতে সাবস্ট্রিং 01 আছে। যেমন, এটি স্ট্রিং 101 বা 0101 গ্রহণ করে। গণনার সব শাখা আমরা সহজেই একটি বৃক্ষ দিয়ে দেখাতে পারি। যেমন, স্ট্রিং 01010 এর জন্য বৃক্ষটি দেখতে এমন হতে পারে:

শুরুতে আমরা আছি প্রারম্ভিক স্টেট q0 এ। ইনপুটে আছে স্ট্রিং 01010, প্রথম না পড়া অক্ষর 0। স্টেট q0 থেকে প্রতীক 0 এর জন্য দুইটি ট্রানজিশন বের হয়েছে, স্টেট q0 ও q1 এ। তাই এই নোডে বৃক্ষের দুইটি সন্তান থাকবে: q0 ও q1। এরপর পড়ি প্রতীক 1। সেখানে কোনো অস্পষ্টতা নেই, আমরা যাই স্টেট q0 ও q2 এ। এরপর পড়ি অক্ষর 0, বাম শাখায় আবার অস্পষ্টতা দেখা দেয়, তাই গণনাকে আরও দুইটি শাখায় ভাগ করি। একটিতে আবার q0 এ থাকি, অন্যটিতে যাই q1 এ। এভাবে চলতে থাকে।

লক্ষ কর, মোট দুইটি শাখা শেষ হয়েছে স্টেট q2 এ, অর্থাৎ চূড়ান্ত স্টেটে। অটোমেটন প্রদত্ত স্ট্রিংটি গ্রহণ করতে পারে, গণনার এমন দুইটি শাখা আছে। তাই এই অটোমেটন স্ট্রিং 01010 গ্রহণ করত। স্ট্রিং 1000 এর জন্যও একই রকম বৃক্ষ বানিয়ে দেখা যাক।

গণনা হয় স্টেট q0 এ থাকে, নয়তো স্টেট q1 এ যায়, কিন্তু সেখান থেকে আর কোথাও যাওয়ার নেই, কারণ ইনপুটে শুধু শূন্য বাকি, আর স্টেট q1 এর ট্রানজিশন আছে শুধু প্রতীক 1 এর জন্য। গণনার কোনো শাখাই চূড়ান্ত স্টেটে শেষ হয় না, তাই অটোমেটন স্ট্রিং 1000 গ্রহণ করে না।

এপসিলন ট্রানজিশন

অনির্ধারণমূলক অটোমেটনে আমরা এপসিলন ট্রানজিশনও ব্যবহার করতে পারি। এগুলো এমন ট্রানজিশন, যা ইনপুটে যে প্রতীকই থাকুক না কেন নেওয়া যায়, এবং তাতে স্ট্রিং থেকে কোনো প্রতীক পড়তে হয় না। এমন একটি অনির্ধারণমূলক অটোমেটন কীভাবে লিখব, যা গ্রহণ করে ফাঁকা স্ট্রিং, শুধু এক দিয়ে গঠিত সব স্ট্রিং, এবং (10)n আকারের স্ট্রিং, অর্থাৎ 10, 1010, …?

অটোমেটনটিকে আমরা দুইটি “উপ-অটোমেটনে” ভাগ করেছি। উপরেরটি শনাক্ত করে 1 দিয়ে গঠিত স্ট্রিং, নিচেরটি (10)n আকারের স্ট্রিং। স্ট্রিং 111 গ্রহণ করে দেখা যাক। শুরুতে অটোমেটন আছে স্টেট q0 এ, ইনপুটে স্ট্রিং 111। এপসিলন ট্রানজিশন থাকায় সে নিজের সুবিধামতো স্টেট q1 বা q2 এ যাওয়ার সিদ্ধান্ত নিতে পারে। দেখতে পাচ্ছি, তার জন্য স্টেট q1 এ যাওয়াই সুবিধাজনক। অটোমেটন সেখানে যায়। অথচ ইনপুটে তখনও আছে স্ট্রিং 111! কেবল এখন থেকে সে স্ট্রিংয়ের প্রতীক পড়তে শুরু করে এবং স্টেট q1 থেকে আবার q1 এ যেতে থাকে, যতক্ষণ না পুরো স্ট্রিং পড়ে তা গ্রহণ করে।

স্ট্রিং 1010 গ্রহণ করার চেষ্টা করলে অটোমেটন শুরুতে যেত স্টেট q2 এ, কেবল সেখান থেকে প্রতীকগুলো প্রক্রিয়া করতে শুরু করত, এবং এবারও স্ট্রিংটি গ্রহণ করত।

স্ট্রিং 1100 এর জন্য অটোমেটন যা খুশি করতে পারে, এমন স্ট্রিং গ্রহণ করার কোনো উপায় তার নেই।

এপসিলন ট্রানজিশন ও অনির্ধারণমূলকতা অনেক ক্ষেত্রে আমাদের কাজ সহজ করে। যেমন, রেগুলার ভাষার সংযোগ আবার রেগুলার ভাষা, এর প্রমাণ এপসিলন ট্রানজিশন দিয়ে নির্ধারণমূলক সসীম অটোমেটনের ক্ষেত্রের চেয়ে অনেক সহজে লেখা যায়। সেই প্রমাণে আমাদের এই অটোমেটনগুলোর উদাহরণ ছিল

এবং

আর তারপর আমরা একটি নির্ধারণমূলক সসীম অটোমেটন গঠন করেছিলাম, যা দুই ভাষার সংযোগ গ্রহণ করত। এপসিলন ট্রানজিশন দিয়ে এমন অটোমেটন এভাবে গঠন করা যায়:

সহজ কথায়, আমরা একটি নতুন প্রারম্ভিক স্টেট যোগ করি, সেখান থেকে দুইটি এপসিলন ট্রানজিশন যাবে মূল অটোমেটন দুইটির প্রারম্ভিক স্টেটে, ব্যস। অটোমেটন অনির্ধারণমূলকভাবে ঠিক করে, স্ট্রিংটি সে একটি “উপ-অটোমেটন” দিয়ে গ্রহণ করার চেষ্টা করবে, নাকি অন্যটি দিয়ে।

অনির্ধারণমূলক অটোমেটনের সংজ্ঞা

নির্ধারণমূলক ও অনির্ধারণমূলক সসীম অটোমেটনের পার্থক্য কোথায়, তা আমরা দেখেছি, বাকি শুধু একে আনুষ্ঠানিক রূপ দেওয়া। নির্ধারণমূলক সসীম অটোমেটনকে আমরা সংজ্ঞায়িত করেছিলাম পঞ্চক ⟨Q, Σ, δ, q0, F⟩ হিসেবে, যেখানে Q স্টেটের সেট, Σ বর্ণমালা, δ ট্রানজিশন ফাংশন, q0 প্রারম্ভিক স্টেট এবং F চূড়ান্ত স্টেটের সেট। অনির্ধারণমূলক অটোমেটনের সংজ্ঞায় বদলায় শুধু ট্রানজিশন ফাংশনের সংজ্ঞা।

নির্ধারণমূলক রূপে δ(q, w) কল করলে ফাংশনটি কেবল একটি স্টেট দিতে পারত, আর অনির্ধারণমূলক রূপে এটি একাধিক স্টেট দিতে পারে, যদি একটি প্রতীকের জন্য একাধিক ট্রানজিশন সংজ্ঞায়িত থাকে। যেহেতু এপসিলন ট্রানজিশনও সংজ্ঞায়িত করতে হবে, তাই সেট Σ ∪ {ε} কে আমরা লিখি Σε, অর্থাৎ Σε = Σ ∪ {ε}। তাই ফাংশন δ এর সংজ্ঞা

δ:Q×Σε→2Q

এখানে 2Q হলো শক্তি সেট, অর্থাৎ সেট Q এর সব উপসেটের সেট। গণনার আনুষ্ঠানিক রূপ সসীম অটোমেটনের মতোই। অটোমেটনের কনফিগারেশন আবার একটি জোড় ⟨q, w⟩ ∈ Q × Σ∗। গণনার ধাপ ↦ হলো কনফিগারেশনের সেটের উপর এমন একটি অন্বয়, যেন

⟨qi,w0w1…wn⟩↦⟨qj,w1…wn⟩,

যদি এবং কেবল যদি qj ∈ δ(qi, w0)। সবচেয়ে বড় পার্থক্য এই বাক্যেই। নির্ধারণমূলক অটোমেটনে এই শর্ত লেখা ছিল qj = δ(qi, w0), কারণ ফাংশন δ সবসময় একটি স্টেট দিত। ট্রানজিশন ফাংশনের অনির্ধারণমূলক রূপ স্টেটের একটি সেট দেয়, তাই সেখানে ∈ প্রতীক। অন্বয়টির স্বসম ও সংক্রমণশীল ক্লোজারকে আবার লিখব ↦ ∗। আমরা বলি, অটোমেটন স্ট্রিং w গ্রহণ করে যদি এবং কেবল যদি এমন qf ∈ F থাকে, যেন

⟨q0,w⟩↦∗⟨qf,ε⟩.

তথ্যসূত্র

সূচিপত্র: সসীম অটোমেটন, সম্পূর্ণ অটোমেটন, অনির্ধারণমূলক সসীম অটোমেটন, অনির্ধারণমূলক অটোমেটনের সিমুলেশন, NFA থেকে DFA তে রূপান্তর