এই সাইটটি বার পঠিত
ভাটিয়ালি | টইপত্তর | বুলবুলভাজা | হরিদাস পাল | খেরোর খাতা | বই
  • খেরোর খাতা

  •  ডিটারমিনিস্টিক ফিনাইট অটোমেটনের গভীরে

    albert banerjee লেখকের গ্রাহক হোন
    ১৫ ফেব্রুয়ারি ২০২৬ | ১০৩ বার পঠিত
  • 00 | 1 | 02 | 003
     রোবটের মনে নিয়মের শৃঙ্খল

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

    মনে করো, সেই বাইনারি বনের রাজা তাঁর রোবটটিকে ডেকে বললেন, রোবট, তুমি তো ভালো কাজ করছ, কিন্তু আমি চাই তোমার কাজের নিয়মগুলো আমি পুরোপুরি বুঝতে পারি। তুমি কীভাবে সিদ্ধান্ত নাও, সেটা কি আমি আগে থেকেই বলে দিতে পারি?

    রোবট বলল, হ্যাঁ রাজা, আপনি আগে থেকেই বলে দিতে পারবেন। আমার প্রতিটি পদক্ষেপ নির্ধারিত। আমি কখনো দ্বিধায় পড়ি না, কখনো একই অবস্থায় থেকে দুই রকমের সিদ্ধান্ত নেই না। আমার পথ সবসময় স্পষ্ট।

    এই যে রোবটের কথা বলল, এটাই হলো ডিটারমিনিস্টিক ফিনাইট অটোমেটনের মূল বৈশিষ্ট্য। ডিটারমিনিস্টিক মানে নিশ্চিত, দ্ব্যর্থহীন। ফিনাইট মানে সসীম, মানে আমার অবস্থার সংখ্যা সীমিত। অটোমেটন মানে যন্ত্র। সব মিলিয়ে ডিএফএ।

    এবার আমরা রোবটটির ভেতরে ঢুকে দেখি। তার ভেতর আছে কতগুলো ঘর। এই ঘরগুলোকেই আমরা বলি অবস্থা। প্রতিটি অবস্থার একটা নাম আছে। যেমন প্রথম অধ্যায়ে আমরা দেখেছিলাম q0, q1, q2 নামে তিনটি অবস্থা। শুরুতে রোবট থাকে q0 ঘরে। তারপর যখন সে কোনো ইনপুট পায়, তখন সে নির্দিষ্ট নিয়মে অন্য ঘরে চলে যায়। এই যে এক ঘর থেকে অন্য ঘরে যাওয়া, একে বলে ট্রানজিশন।

    এখন প্রশ্ন হলো, এই ট্রানজিশনের নিয়ম কে বানায়? রাজা বানায়। রাজা ঠিক করে দেন, কোন অবস্থা থেকে কোন ইনপুট পড়লে কোন অবস্থায় যেতে হবে। যেমন রাজা বললেন, q0 ঘরে থাকা অবস্থায় যদি ০ পড়ো, তাহলে q1 ঘরে যাবে। আর যদি ১ পড়ো, তাহলে q0-তেই থাকবে। এটা পুরোপুরি রাজার হাতে। রোবটের নিজের কোনো ইচ্ছে নেই। সে শুধু রাজার দেওয়া নিয়ম মেনে চলে।

    এখন ধরো, তুমি রোবটকে একটি স্ট্রিং দিলে। যেমন ০১১০। রোবট প্রথমে q0-তে থাকে। প্রথম চিহ্ন ০ পড়ে, নিয়ম অনুযায়ী চলে যায় q1-এ। দ্বিতীয় চিহ্ন ১ পড়ে, এখন সে q1-এ আছে। q1-এ থাকা অবস্থায় ১ পড়ার নিয়ম কী? রাজা বলে দিয়েছেন, q1-এ ১ পড়লে যেতে হবে q2-তে। তাহলে রোবট চলে গেল q2-তে। তৃতীয় চিহ্ন ১ পড়ে, এখন q2-এ আছে। q2-এ ১ পড়ার নিয়ম হলো q0-তে যাওয়া। তাহলে রোবট চলে গেল q0-তে। চতুর্থ চিহ্ন ০ পড়ে, q0-এ ০ পড়ার নিয়ম হলো q1-এ যাওয়া। তাহলে রোবট চলে গেল q1-এ। স্ট্রিং শেষ। এখন রোবট আছে q1-এ।

    রাজার ভাষা যদি হয় শেষে ০১-ওয়ালা স্ট্রিং, তাহলে q2 ছিল স্বীকৃত অবস্থা। কিন্তু রোবট এখন q1-এ, যা স্বীকৃত নয়। তাই রোবট বলবে, এই স্ট্রিং রাজার ভাষার বাইরে।

    এভাবে প্রতিটি স্ট্রিং-এর জন্য রোবট একটি নির্দিষ্ট পথ অনুসরণ করে। এই পথ কখনো বদলায় না। একই স্ট্রিং দিলে একই পথে যাবে, একই সিদ্ধান্ত দেবে। এটাই ডিটারমিনিজম।

    এবার আমরা একটু ভিন্ন ভাষা নিয়ে ভাবি। রাজা বললেন, আমি চাই যেসব স্ট্রিং-এর শুরু ০ এবং শেষ ১, সেগুলো আমার ভাষা। যেমন ০১, ০০১, ০১১, ০১০১ এরা গ্রহণযোগ্য। আর ১১, ১০, ০০, ১০১০ এরা নয়।

    এই ভাষার জন্য রোবটের কয়টি অবস্থা দরকার? শুরুতে আমরা চিন্তা করি। প্রথম শর্ত হলো শুরু ০ হতে হবে। তার মানে প্রথম ইনপুট যদি ১ হয়, তাহলে সেটা সঙ্গে সঙ্গেই বাতিল। কিন্তু রোবট তো স্ট্রিং শেষ হওয়ার আগে কিছু বলতে পারে না। তাই তাকে স্ট্রিং শেষ পর্যন্ত পড়তে হবে, তারপর সিদ্ধান্ত নিতে হবে।

    তাহলে আমরা অবস্থাগুলো ঠিক করি। প্রথম অবস্থা q0, শুরুর অবস্থা। এখানে থাকা মানে আমরা এখনো প্রথম চিহ্ন দেখিনি। তারপর প্রথম চিহ্ন যদি ০ হয়, তাহলে আমরা যাই q1-এ। প্রথম চিহ্ন যদি ১ হয়, তাহলে আমরা যাই q2-তে, যে অবস্থা থেকে আর ফেরার পথ নেই, কারণ শুরু ১ হয়ে গেছে, যা আমাদের ভাষার জন্য অগ্রহণযোগ্য।

    q1-এ থাকা মানে আমরা শুরু ০ দেখেছি এবং এখন স্ট্রিং-এর বাকি অংশ পড়ছি। এখানে আমরা যেকোনো চিহ্ন পড়তে থাকি, কিন্তু শেষ চিহ্নটা ১ হতে হবে। তাহলে আমরা কীভাবে বুঝব শেষ চিহ্নটা কী?

    আমরা q1-কে দুভাগে ভাগ করতে পারি। q1-এ থাকা মানে শেষ দেখা চিহ্ন ০। আরেকটি অবস্থা q3, এখানে থাকা মানে শেষ দেখা চিহ্ন ১। তাহলে q1-এ থাকা অবস্থায় যদি ০ পড়ি, থাকি q1-তেই। যদি ১ পড়ি, যাই q3-তে। q3-এ থাকা অবস্থায় যদি ০ পড়ি, যাই q1-তে। যদি ১ পড়ি, থাকি q3-তেই।

    এখন স্বীকৃত অবস্থা কোনটি? আমাদের ভাষার স্ট্রিং-এর শেষ চিহ্ন ১ হতে হবে। তাই স্ট্রিং শেষে যদি আমরা q3-এ থাকি, তাহলে সেটি গ্রহণযোগ্য। আর q2-তে থাকলে বা q1-তে থাকলে অগ্রহণযোগ্য।

    কিন্তু q2-এর কথা ভুলে গেলে চলবে না। q2 হলো সেই অবস্থা, যেখানে আমরা প্রথম চিহ্ন ১ দেখে চলে এসেছি। সেখানে থেকে যেকোনো চিহ্ন পড়লেই আমরা q2-তেই থাকব, কারণ একবার ভুল হয়ে গেলে আর ফেরার নেই।

    তাহলে আমাদের অবস্থা চারটি: q0 (শুরু), q1 (শেষ দেখা চিহ্ন ০ এবং শুরু ০ ছিল), q3 (শেষ দেখা চিহ্ন ১ এবং শুরু ০ ছিল), q2 (ভুল পথ, শুরু ১ ছিল)।

    এখন ট্রানজিশনগুলো দাঁড়ায়:
    q0-এ ০ পড়লে q1, ১ পড়লে q2।
    q1-এ ০ পড়লে q1, ১ পড়লে q3।
    q3-এ ০ পড়লে q1, ১ পড়লে q3।
    q2-এ ০ পড়লে q2, ১ পড়লে q2।
    স্বীকৃত অবস্থা: q3।

    এখন তুমি যদি ০১০১ স্ট্রিংটি দাও, তাহলে কী হবে?
    q0 থেকে শুরু, ০ পড়ে q1, ১ পড়ে q3, ০ পড়ে q1, ১ পড়ে q3। শেষ অবস্থা q3, স্বীকৃত। তাই ঠিক আছে।

    আর ১০১০ দিলে? q0 থেকে শুরু, ১ পড়ে q2, ০ পড়ে q2, ১ পড়ে q2, ০ পড়ে q2। শেষ অবস্থা q2, স্বীকৃত নয়। তাই বাতিল।

    এভাবেই ডিএফএ কাজ করে।

    এবার আমরা বুঝতে চেষ্টা করি, ডিএফএ-র পাঁচটি জিনিস সবসময় থাকে। প্রথমত, অবস্থার সেট। দ্বিতীয়ত, বর্ণমালা। তৃতীয়ত, ট্রানজিশন ফাংশন। চতুর্থত, শুরুর অবস্থা। পঞ্চমত, স্বীকৃত অবস্থার সেট। এই পাঁচটি জিনিস একসাথে থাকলেই একটি ডিএফএ তৈরি হয়।

    এখন রোবটটিকে কিন্তু আমরা চাইলেই প্রোগ্রাম করতে পারি। যেমন আমরা প্রথম অধ্যায়ে পাইথন কোড দেখেছিলাম। সেখানে ডিএফএ ক্লাস বানানো ছিল, যার মধ্যে এই পাঁচটি জিনিস রাখা যায়। তারপর অ্যাকসেপ্টস মেথডে একটি স্ট্রিং দিয়ে বলা যায়, সেটি স্বীকৃত কি না।

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

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

    রাজা বললেন, তুমি একটি বিশেষ অবস্থা রাখতে পার, যেখানে সব অচেনা চিহ্ন গিয়ে পড়বে। এবং একবার সেখানে গেলে আর ফেরার পথ নেই। যেমন আমরা আগে q2 বানিয়েছিলাম ভুল পথের জন্য। সেরকম একটা অবস্থা বানিয়ে রাখো। যেকোনো অচেনা চিহ্ন পেলেই সেখানে চলে যাবে।

    রোবট তা-ই করল। এখন থেকে বর্ণমালার বাইরের কোনো চিহ্ন পেলে সে সঙ্গে সঙ্গে একটি বিশেষ অবস্থায় চলে যায় এবং সেখানেই থেকে যায়। স্ট্রিং শেষে যদি সেই অবস্থায় থাকে, তাহলে বলবে ভাষার বাইরে।

    এটা হলো ডিএফএ-র আরেকটি গুরুত্বপূর্ণ বৈশিষ্ট্য। এটা সবসময় সব ইনপুটের জন্য একটি নির্দিষ্ট পথ বেছে নেয়। কখনো থেমে যায় না, কখনো দ্বিধায় পড়ে না। ইনপুট পড়তে পড়তে এগিয়ে চলে, শেষ পর্যন্ত পৌঁছে সিদ্ধান্ত নেয়।

    এখন আমরা একটু ভিন্ন ভাবনা করি। রোবট কি সবসময় ছোট ছোট ভাষার জন্য কাজ করে? না, রোবট অনেক বড় ভাষাও চিনতে পারে। যেমন ধরো, রাজা বললেন, আমি চাই যেসব বাইনারি স্ট্রিং-এ ০-এর সংখ্যা জোড় এবং ১-এর সংখ্যাও জোড়, সেগুলো আমার ভাষা। এটা কিন্তু বেশ জটিল ভাষা।

    এর জন্য রোবটের কয়টি অবস্থা দরকার? আমাদের মনে রাখতে হবে, ০-এর সংখ্যা জোড় না বিজোড়, আর ১-এর সংখ্যা জোড় না বিজোড়, এই দুই বিষয় মিলিয়ে মোট চারটি সম্ভাবনা আছে। যেমন:
    - ০ জোড়, ১ জোড়
    - ০ জোড়, ১ বিজোড়
    - ০ বিজোড়, ১ জোড়
    - ০ বিজোড়, ১ বিজোড়

    তাহলে আমাদের চারটি অবস্থা দরকার। শুরুতে ০ ও ১ দুটোই জোড়, তাই শুরু অবস্থা হবে প্রথমটি। তারপর প্রতিটি ইনপুটের সঙ্গে সঙ্গে অবস্থা বদলাবে। যেমন ০ পড়লে ০-এর সংখ্যা বদলে যায়, ১ পড়লে ১-এর সংখ্যা বদলে যায়। কাজেই ট্রানজিশন ঠিক করে ফেলা যায়।

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

    এবার আসি একটি মজার বিষয়ে। রোবট তো সব সময় একই নিয়মে চলে। কিন্তু যদি রোবটের ভেতর একটু গোলমাল হয়, তাহলে কী হবে? যেমন কখনো কখনো ০ পড়ে সে ১-এর ট্রানজিশন নিয়ে ফেলে। সেক্ষেত্রে সে ভুল পথে চলে যাবে। কিন্তু যেহেতু সে ডিটারমিনিস্টিক, তাই তার কোনো উপায় নেই ভুল শোধরানোর। একবার ভুল পথে গেলে শেষ পর্যন্ত ভুলই থাকবে।

    এই কারণে ডিএফএ বানানোর সময় খুব সতর্ক থাকতে হয়। প্রতিটি ট্রানজিশন ঠিকভাবে দিতে হয়। আর নিশ্চিত করতে হয় যে প্রতিটি অবস্থা থেকে প্রতিটি ইনপুটের জন্য একটি এবং কেবল একটি ট্রানজিশন আছে। যদি কোনো অবস্থা থেকে কোনো ইনপুটের জন্য ট্রানজিশন না থাকে, তাহলে সেটি ডিএফএ নয়। সেক্ষেত্রে আমরা একটি ডেড অবস্থা বানিয়ে নিতে পারি, যেখানে সব অজানা ট্রানজিশন চলে যাবে।

    এখন আমরা আরেকটি উদাহরণ দেখি। ধরো, রাজা বললেন, আমি চাই যেসব স্ট্রিং-এ ঠিক দুটি ১ আছে, সেগুলো আমার ভাষা। যেমন ০১০, ১০০, ০০১১০ এরা গ্রহণযোগ্য। কিন্তু ১১১, ১০১০, ০০০ এরা নয়।

    এটার জন্য আমরা অবস্থা বানাতে পারি। শুরু অবস্থা q0, মানে এখনো কোনো ১ দেখিনি। তারপর q1, মানে একটি ১ দেখেছি। তারপর q2, মানে দুটি ১ দেখেছি। তারপর q3, মানে দুটির বেশি ১ দেখেছি। q3 হবে ডেড অবস্থা। এখন ট্রানজিশন: q0-এ ০ পড়লে থাকি q0-তে, ১ পড়লে যাই q1-এ। q1-এ ০ পড়লে থাকি q1-তে, ১ পড়লে যাই q2-তে। q2-এ ০ পড়লে থাকি q2-তে, ১ পড়লে যাই q3-তে। q3-এ যেকোনো কিছু পড়লে থাকি q3-তে। স্বীকৃত অবস্থা q2।

    এটা খুব সহজ।

    এবার একটি বিশেষ ভাষা দেখি। রাজা বললেন, আমি চাই যেসব স্ট্রিং-এর দৈর্ঘ্য ৩ দিয়ে বিভাজ্য, সেগুলো আমার ভাষা। যেমন ০০০, ১১১, ০১০, এরা দৈর্ঘ্য ৩, ৩, ৩, তাই গ্রহণযোগ্য। কিন্তু ০১, ১০১০, এরা দৈর্ঘ্য ২ ও ৪, তাই নয়।

    এর জন্য আমাদের দরকার তিনটি অবস্থা। এক অবস্থা যেখানে দৈর্ঘ্য ৩ দিয়ে ভাগ করলে ভাগশেষ ০, আরেকটি যেখানে ভাগশেষ ১, আরেকটি যেখানে ভাগশেষ ২। শুরুতে দৈর্ঘ্য ০, ভাগশেষ ০, তাই শুরু অবস্থা হবে ভাগশেষ ০-এর অবস্থা। তারপর প্রতিটি চিহ্ন পড়ার সঙ্গে সঙ্গে ভাগশেষ এক করে বাড়বে। যেমন ভাগশেষ ০ থেকে ১ পড়লে ভাগশেষ ১, ১ থেকে ১ পড়লে ভাগশেষ ২, ২ থেকে ১ পড়লে ভাগশেষ ০। ০ চিহ্ন পড়লেও একই নিয়ম, কারণ দৈর্ঘ্য বাড়ে, চিহ্ন কী তা বিবেচ্য না।

    তাহলে ট্রানজিশন: q0-এ ০ বা ১ পড়লে q1, q1-এ ০ বা ১ পড়লে q2, q2-এ ০ বা ১ পড়লে q0। স্বীকৃত অবস্থা q0।

    এখানে লক্ষণীয়, চিহ্নের মান এখানে গুরুত্বপূর্ণ নয়, শুধু দৈর্ঘ্য গুরুত্বপূর্ণ। তাই আমরা চিহ্ন নির্বিশেষে একই ট্রানজিশন দিয়েছি।

    এখন আমরা যদি এই ডিএফএ-কে পাইথনে বাস্তবায়ন করি, তাহলে সেটা খুব সহজ। আমরা প্রথম অধ্যায়ের ক্লাসটাই ব্যবহার করতে পারি। শুধু ট্রানজিশন টেবিলটা ঠিক করে দিতে হবে।

    কিন্তু আমরা এখন গল্পেই থাকি। আমাদের রোবটটি কিন্তু দিনরাত কাজ করে যাচ্ছে। সে কখনো ক্লান্ত হয় না, কখনো ভুল করে না। তার কাজ পুরোপুরি নিশ্চিত। এটাই ডিএফএ-র সৌন্দর্য।

    এবার আসি বাস্তব জীবনের উদাহরণে। ধরো, তুমি একটি ইমেল রিডার বানাচ্ছো। এই ইমেল রিডার-এর কাজ হলো, ব্যবহারকারী যখন ইমেল ঠিকানা দেয়, তখন সেটি বৈধ কি না, তা যাচাই করা। যেমন example@domain.com এটি বৈধ, কিন্তু example@domain, বা example.com এটি বৈধ নয়।

    ইমেল ঠিকানা যাচাই করার জন্য আমরা একটি ডিএফএ বানাতে পারি। ইমেল ঠিকানার গঠন সাধারণত এরকম: লোকালপার্ট @ ডোমেইন . টপলেভেলডোমেইন। লোকালপার্ট-এ থাকতে পারে অক্ষর, সংখ্যা, ডট, আন্ডারস্কোর ইত্যাদি। কিন্তু ডট পরপর দুইবার থাকতে পারে না, এবং ডট শুরুতে বা শেষে থাকতে পারে না। ডোমেইন-এ থাকে অক্ষর, সংখ্যা, হাইফেন, কিন্তু হাইফেন শুরুতে বা শেষে থাকে না। টপলেভেলডোমেইন সাধারণত দুই থেকে ছয় অক্ষরের হয়।

    এত জটিল নিয়মের জন্যও আমরা একটি ডিএফএ বানাতে পারি। তার জন্য অনেকগুলো অবস্থা দরকার। যেমন শুরু অবস্থা, তারপর লোকালপার্ট-এর বিভিন্ন অবস্থা, তারপর @ চিহ্নের জন্য অবস্থা, তারপর ডোমেইন-এর বিভিন্ন অবস্থা, তারপর ডট-এর জন্য অবস্থা, তারপর টিএলডি-র জন্য অবস্থা। প্রতিটি অবস্থা থেকে নির্দিষ্ট চিহ্ন পড়লে নির্দিষ্ট অবস্থায় যেতে হবে। আর শেষে যদি সঠিক অবস্থায় থাকি, তাহলে ইমেল বৈধ।

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

    তবে আমাদের গল্পের রোবটটি শুধু ইমেল নয়, আরও অনেক কিছু চিনতে পারে। যেমন ওয়েব ঠিকানা, ফোন নম্বর, পিন কোড, সবকিছুর জন্যই আলাদা আলাদা ডিএফএ বানানো যায়।

    এখন প্রশ্ন হলো, ডিএফএ কি সব ভাষা চিনতে পারে? না। অনেক ভাষা আছে যা ডিএফএ চিনতে পারে না। যেমন সমান সংখ্যক ০ আর ১-এর ভাষা, যেমন ০১, ০০১১, ০০০১১১ ইত্যাদি। এই ভাষা চিনতে হলে আমাদের মনে রাখতে হবে কতগুলো ০ দেখেছি, যাতে পরে ঠিক ততগুলো ১ দেখতে পারি। কিন্তু ডিএফএ-র তো সীমিত স্মৃতি, সে অসীম সংখ্যা মনে রাখতে পারে না। তাই এই ভাষা ডিএফএ-র বাইরে।

    এজন্য পরে আমরা পুশডাউন অটোমেটন দেখব, যেখানে স্ট্যাক থাকে, সেখানে অসীম সংখ্যা মনে রাখা যায়।

    কিন্তু আপাতত আমরা ডিএফএ-তেই থাকি। ডিএফএ-র সবচেয়ে বড় ব্যবহার হলো লেক্সিক্যাল অ্যানালাইসিসে। কম্পাইলার যখন তোমার কোড পড়ে, প্রথমে সে কোডটাকে ছোট ছোট টোকেনে ভাগ করে। যেমন if, while, for, variable name, number, operator ইত্যাদি। এই টোকেনগুলো চিনতে ডিএফএ ব্যবহার হয়। যেমন সংখ্যা চেনার জন্য ডিএফএ: প্রথমে একটা সংখ্যা, তারপর আরও সংখ্যা, তারপর দশমিক বিন্দু, তারপর আরও সংখ্যা, এইভাবে।

    এমনিভাবে প্রতিটি টোকেনের জন্য আলাদা ডিএফএ বানানো যায়। আর এই ডিএফএ-গুলো একসাথে চালিয়ে কোড থেকে টোকেন বের করা যায়।

    এবার আমরা যদি নিজেরা একটি ছোট লেক্সিক্যাল অ্যানালাইজার বানাতে চাই, তাহলে কী করতে হবে? প্রথমে আমাদের ভাষার টোকেনগুলো ঠিক করতে হবে। যেমন আমাদের ভাষায় শুধু সংখ্যা আর প্লাস চিহ্ন আছে। সংখ্যা হলো এক বা একাধিক ডিজিট। প্লাস চিহ্ন হলো +। তাহলে ডিএফএ বানাতে হবে সংখ্যা চেনার জন্য আর প্লাস চিহ্ন চেনার জন্য।

    সংখ্যা চেনার ডিএফএ: শুরু অবস্থা, প্রথম ডিজিট পেলে সংখ্যা অবস্থায় যাই, তারপর যেকোনো ডিজিট পেলে সেখানেই থাকি। অন্য কোনো চিহ্ন পেলে ডেড অবস্থায় যাই।

    প্লাস চিহ্ন চেনার ডিএফএ: শুরু অবস্থা, + পেলে স্বীকৃত অবস্থায় যাই, অন্য কোনো চিহ্ন পেলে ডেড অবস্থায় যাই।

    এই দুই ডিএফএ একসাথে চালিয়ে আমরা ইনপুট স্ট্রিং থেকে টোকেনগুলো বের করতে পারি। যেমন ১২৩+৪৫৬ এই স্ট্রিং থেকে প্রথমে ১২৩ সংখ্যা, তারপর +, তারপর ৪৫৬ সংখ্যা বের করবে।

    এটাই লেক্সিক্যাল অ্যানালাইসিসের মূল কথা।

    এখন আমরা ডিএফএ-র কিছু মজার বৈশিষ্ট্য দেখি। ডিএফএ-র সংখ্যা কিন্তু সীমিত। একটা ভাষার জন্য অনেকগুলো ডিএফএ থাকতে পারে, কিন্তু সবচেয়ে ছোট ডিএফএ-টাকে বলে মিনিমাল ডিএফএ। এই মিনিমাল ডিএফএ বের করার পদ্ধতি আছে, যার নাম ডিএফএ মিনিমাইজেশন। এটা কাজে লাগে যখন আমরা একটি ডিএফএ বানিয়ে ফেলি, কিন্তু সেটাতে অপ্রয়োজনীয় অবস্থা থাকে, তখন সেগুলো বাদ দিয়ে ছোট করা যায়।

    আরেকটি মজার বিষয় হলো, ডিএফএ আর এনএফএ কিন্তু সমান শক্তির। প্রতিটি এনএফএ-কে ডিএফএ-তে রূপান্তর করা যায়, যদিও সেটাতে অবস্থার সংখ্যা অনেক বেড়ে যেতে পারে। এই রূপান্তরের পদ্ধতির নাম সাবসেট কনস্ট্রাকশন।

    কিন্তু আমরা এখন গল্পেই ফিরে যাই। আমাদের রোবটটি দিনশেষে বিশ্রাম নেয়। সে জানে, আগামীকাল আবার নতুন স্ট্রিং আসবে, নতুন ভাষা আসবে, আর তাকে সেগুলো চিনতে হবে। কিন্তু সে প্রস্তুত। তার ভেতরের নিয়মগুলো স্পষ্ট, তার পথগুলো নির্ধারিত। সে কখনো ভুল করে না, কখনো দ্বিধায় পড়ে না।

    এটাই ডিটারমিনিস্টিক ফিনাইট অটোমেটন। নিশ্চিত, দ্ব্যর্থহীন, সীমিত অবস্থার যন্ত্র।

    এখন শেষ করি একটি বাস্তব উদাহরণ দিয়ে। তুমি যদি একটি ইমেল রিডার বানাতে চাও যা ইমেল ঠিকানা যাচাই করে, তাহলে তুমি নিচের নিয়মে একটি ডিএফএ বানাতে পারো:

    শুরু অবস্থা থেকে, অক্ষর বা সংখ্যা পেলে লোকালপার্ট-১ অবস্থায় যাবে। সেখানে থেকে অক্ষর বা সংখ্যা পেলে সেখানেই থাকবে, ডট পেলে লোকালপার্ট-ডট অবস্থায় যাবে। লোকালপার্ট-ডট থেকে আবার অক্ষর বা সংখ্যা পেলে লোকালপার্ট-১-এ ফিরে যাবে। এভাবে চলতে থাকবে। তারপর @ পেলে ডোমেইন শুরু অবস্থায় যাবে। ডোমেইন-এ অক্ষর বা সংখ্যা পেলে ডোমেইন-১ অবস্থায় যাবে। সেখানে থেকে অক্ষর বা সংখ্যা পেলে সেখানেই থাকবে, হাইফেন পেলে ডোমেইন-হাইফেন অবস্থায় যাবে। ডোমেইন-হাইফেন থেকে আবার অক্ষর বা সংখ্যা পেলে ডোমেইন-১-এ ফিরে যাবে। তারপর ডট পেলে টিএলডি শুরু অবস্থায় যাবে। টিএলডি-তে অক্ষর পেলে টিএলডি-১, টিএলডি-২ ইত্যাদি অবস্থায় যাবে। সর্বোচ্চ ছয়টি অক্ষর পর্যন্ত যেতে পারে। তারপর স্ট্রিং শেষে যদি টিএলডি-১ থেকে টিএলডি-৬-এর মধ্যে কোনো অবস্থায় থাকি, তাহলে ইমেল বৈধ।

    এভাবে জটিল ইমেল যাচাইকরণও ডিএফএ দিয়ে করা যায়। আর এটা ঠিক আমাদের রোবটের কাজের মতোই।

    তাই ডিএফএ শুধু তত্ত্ব নয়, বাস্তব ইঞ্জিনিয়ারিং-এর একটি অপরিহার্য হাতিয়ার।
     
    পুনঃপ্রকাশ সম্পর্কিত নীতিঃ এই লেখাটি ছাপা, ডিজিটাল, দৃশ্য, শ্রাব্য, বা অন্য যেকোনো মাধ্যমে আংশিক বা সম্পূর্ণ ভাবে প্রতিলিপিকরণ বা অন্যত্র প্রকাশের জন্য গুরুচণ্ডা৯র অনুমতি বাধ্যতামূলক। লেখক চাইলে অন্যত্র প্রকাশ করতে পারেন, সেক্ষেত্রে গুরুচণ্ডা৯র উল্লেখ প্রত্যাশিত।
    00 | 1 | 02 | 003
  • মতামত দিন
  • বিষয়বস্তু*:
  • albert banerjee | ১৫ ফেব্রুয়ারি ২০২৬ ০২:০৭738499
  • from collections import defaultdict

    class DFA:
        # ...
        def minimize(self):
            # Hopcroft's algorithm simplified
            states = list(self.states)
            alphabet = list(self.alphabet)
           
            # Initial partitions: accept and non-accept
            P = [set(self.accept), set(self.states) - set(self.accept)]
            P = [p for p in P if p]  # remove empty
           
            while True:
                new_P = []
                for group in P:
                    for a in alphabet:
                        # Group by where they go on 'a'
                        trans = defaultdict(list)
                        for s in group:
                            next_s = self.transition[s][a]
                            for i, g in enumerate(P):
                                if next_s in g:
                                    trans[i].append(s)
                                    break
                        if len(trans) > 1:
                            new_P.extend(trans.values())
                            break
                    else:
                        new_P.append(group)
                if len(new_P) == len(P):
                    break
                P = new_P
           
            # Remap states
            state_map = {}
            new_states = []
            for i, group in enumerate(P):
                rep = min(group)  # choose representative
                new_states.append(rep)
                for s in group:
                    state_map[s] = rep
           
            # Build new transition
            new_trans = {}
            for s in new_states:
                new_trans[s] = {a: state_map[self.transition[s][a]] for a in alphabet}
           
            new_start = state_map[self.start]
            new_accept = {state_map[s] for s in self.accept if state_map[s] in new_states}
           
            return DFA(set(new_states), set(alphabet), new_trans, new_start, new_accept)

    টেস্ট
     উদাহরণ ১ দিয়ে চেক করুন — এটা ইতিমধ্যে মিনিমাল

     
  • যামিনী রায় | 2601:5c0:c280:d900:419:ff14:fa86:***:*** | ১৫ ফেব্রুয়ারি ২০২৬ ০৬:০৩738510
  • এই লেখাটি ডিটারমিনিস্টিক ফিনাইট অটোমেটন (DFA) সম্পর্কে অত্যন্ত সুন্দর ও সহজবোধ্য একটি ব্যাখ্যা উপস্থাপন করেছে। বাইনারি বনের রাজা এবং রোবটের রূপকের মাধ্যমে জটিল তাত্ত্বিক ধারণাগুলোকে গল্পের আকারে তুলে ধরার প্রয়াস প্রশংসনীয়। এই পদ্ধতিতে DFA-র মূল বৈশিষ্ট্যগুলো—ডিটারমিনিজম, সসীম অবস্থা, ট্রানজিশন ফাংশন—সবই পরিষ্কারভাবে উপস্থাপিত হয়েছে।

    বিশেষত, লেখক যেভাবে প্রতিটি উদাহরণ ধাপে ধাপে বিশ্লেষণ করেছেন, তা শিক্ষার্থীদের জন্য অত্যন্ত উপকারী। শুরু ০ এবং শেষ ১-এর ভাষার জন্য চারটি অবস্থার প্রয়োজন কেন, এবং কীভাবে প্রতিটি ট্রানজিশন নির্ধারণ করতে হয়, তার ব্যাখ্যা যথেষ্ট স্বচ্ছ। একইভাবে, ঠিক দুটি ১ সংবলিত স্ট্রিং কিংবা দৈর্ঘ্য ৩ দিয়ে বিভাজ্য স্ট্রিং-এর উদাহরণগুলো DFA ডিজাইনের বিভিন্ন দিক তুলে ধরে।

    তবে কিছু বিষয়ে আরও গভীরতা আনা যেত। যেমন, DFA-র পাঁচটি উপাদান—অবস্থার সেট (Q), বর্ণমালা (Σ), ট্রানজিশন ফাংশন (δ), শুরুর অবস্থা (q₀), এবং স্বীকৃত অবস্থার সেট (F)—এগুলোর আনুষ্ঠানিক গাণিতিক সংজ্ঞা উল্লেখ করা হলে লেখাটি আরও পূর্ণাঙ্গ হতো। আনুষ্ঠানিক ভাষা তত্ত্বে এই টাপল (Q, Σ, δ, q₀, F) দিয়ে DFA প্রকাশ করা হয়, যা পাঠকদের একাডেমিক সাহিত্যের সাথে সংযোগ স্থাপনে সহায়ক হতো।
    লেখায় DFA-র সীমাবদ্ধতার কথা উল্লেখ করা হয়েছে, বিশেষত সমান সংখ্যক ০ ও ১ সংবলিত ভাষার উদাহরণ দিয়ে। এখানে পাম্পিং লেমা (Pumping Lemma for Regular Languages) উল্লেখ করা যেত, যা আনুষ্ঠানিকভাবে প্রমাণ করে যে কিছু ভাষা রেগুলার নয়। এই লেমা ব্যবহার করে দেখানো যায় যে {0ⁿ1ⁿ | n ≥ 0} ভাষাটি কোনো DFA দিয়ে স্বীকৃত করা সম্ভব নয়।

    লেক্সিক্যাল অ্যানালাইসিসে DFA-র ব্যবহার নিয়ে যে আলোচনা করা হয়েছে, তা অত্যন্ত প্রাসঙ্গিক এবং বাস্তবমুখী। কম্পাইলার ডিজাইনের প্রথম পর্যায়ে টোকেনাইজেশনের জন্য DFA অপরিহার্য। তবে এখানে রেগুলার এক্সপ্রেশন থেকে DFA তৈরির পদ্ধতি—যেমন থম্পসন কনস্ট্রাকশন বা সরাসরি কনস্ট্রাকশন—সংক্ষেপে উল্লেখ করা যেত। এছাড়া, lex বা flex এর মতো লেক্সার জেনারেটর টুলস কীভাবে DFA ব্যবহার করে, তার উল্লেখ পাঠকদের বাস্তব প্রয়োগ সম্পর্কে আরও ধারণা দিত।

    DFA মিনিমাইজেশনের কথা সংক্ষেপে এসেছে, কিন্তু মাইহিল-নেরোড থিওরেম (Myhill-Nerode Theorem) এবং টেবল-ফিলিং অ্যালগোরিদম বা পার্টিশন রিফাইনমেন্ট পদ্ধতির উল্লেখ থাকলে বিষয়টি আরও স্পষ্ট হতো। মিনিমাল DFA একক এবং ক্যানোনিক্যাল—এই গুরুত্বপূর্ণ তথ্যটিও যোগ করা যেত।

    ইমেল ভ্যালিডেশনের উদাহরণটি চমৎকার, তবে বাস্তবে ইমেল ঠিকানার RFC 5322 স্ট্যান্ডার্ড অত্যন্ত জটিল এবং সম্পূর্ণ স্ট্যান্ডার্ড মেনে ভ্যালিডেশন করতে শুধু DFA যথেষ্ট নয়—কনটেক্সট-ফ্রি গ্রামার প্রয়োজন হতে পারে। তবে সরলীকৃত ইমেল ফরম্যাট যাচাইয়ে DFA কার্যকর, এবং এই দিকটি লেখায় ভালোভাবে উপস্থাপিত হয়েছে।
    সামগ্রিকভাবে, এই লেখাটি DFA সম্পর্কে প্রাথমিক ও মধ্যম পর্যায়ের শিক্ষার্থীদের জন্য একটি চমৎকার সম্পদ। গল্পের মাধ্যমে তত্ত্ব শেখানোর এই পদ্ধতি বাংলা ভাষায় কম্পিউটার বিজ্ঞানের জটিল বিষয় সহজীকরণের একটি উল্লেখযোগ্য প্রচেষ্টা। ভবিষ্যতে এই ধারাবাহিকে NFA, রেগুলার এক্সপ্রেশন, পুশডাউন অটোমেটা এবং টুরিং মেশিনের মতো বিষয়গুলোও এভাবে উপস্থাপিত হলে বাংলা ভাষায় থিওরি অফ কম্পিউটেশনের একটি সমৃদ্ধ সংগ্রহ তৈরি হবে।
  • তথ্যসমৃদ্ধ  | 165.225.***.*** | ১৫ ফেব্রুয়ারি ২০২৬ ০৮:৫১738511
  • কেন যামিনী না যেতে জ্বালালে না 
  • albert banerjee | ১৫ ফেব্রুয়ারি ২০২৬ ১০:৪০738513
  • থ্যাংক ইউ স্যার এই লেখাটা আলফা জেনেরেশন এর জন্য যাদের মাক্সিনাম বয়স ১৪ থেকে ১৫। আমি শুধু তাদের মধ্যে আগ্রহ জাগাবার চেষ্টা করছি। ভবিষ্যতে এই ধারাবাহিকে NFA, রেগুলার এক্সপ্রেশন, পুশডাউন অটোমেটা এবং টুরিং মেশিনের মতো বিষয়গুলোও থাকবে . তবে সমালোচনা খুব  প্ৰয়োজন হ্যা আপনি খুব সত্যি ভাবেই করেছেন।  
  • মতামত দিন
  • বিষয়বস্তু*:
এই সাইটটি বার পঠিত
  • কি, কেন, ইত্যাদি
  • বাজার অর্থনীতির ধরাবাঁধা খাদ্য-খাদক সম্পর্কের বাইরে বেরিয়ে এসে এমন এক আস্তানা বানাব আমরা, যেখানে ক্রমশ: মুছে যাবে লেখক ও পাঠকের বিস্তীর্ণ ব্যবধান। পাঠকই লেখক হবে, মিডিয়ার জগতে থাকবেনা কোন ব্যকরণশিক্ষক, ক্লাসরুমে থাকবেনা মিডিয়ার মাস্টারমশাইয়ের জন্য কোন বিশেষ প্ল্যাটফর্ম। এসব আদৌ হবে কিনা, গুরুচণ্ডালি টিকবে কিনা, সে পরের কথা, কিন্তু দু পা ফেলে দেখতে দোষ কী? ... আরও ...
  • আমাদের কথা
  • আপনি কি কম্পিউটার স্যাভি? সারাদিন মেশিনের সামনে বসে থেকে আপনার ঘাড়ে পিঠে কি স্পন্ডেলাইটিস আর চোখে পুরু অ্যান্টিগ্লেয়ার হাইপাওয়ার চশমা? এন্টার মেরে মেরে ডান হাতের কড়ি আঙুলে কি কড়া পড়ে গেছে? আপনি কি অন্তর্জালের গোলকধাঁধায় পথ হারাইয়াছেন? সাইট থেকে সাইটান্তরে বাঁদরলাফ দিয়ে দিয়ে আপনি কি ক্লান্ত? বিরাট অঙ্কের টেলিফোন বিল কি জীবন থেকে সব সুখ কেড়ে নিচ্ছে? আপনার দুশ্‌চিন্তার দিন শেষ হল। ... আরও ...
  • বুলবুলভাজা
  • এ হল ক্ষমতাহীনের মিডিয়া। গাঁয়ে মানেনা আপনি মোড়ল যখন নিজের ঢাক নিজে পেটায়, তখন তাকেই বলে হরিদাস পালের বুলবুলভাজা। পড়তে থাকুন রোজরোজ। দু-পয়সা দিতে পারেন আপনিও, কারণ ক্ষমতাহীন মানেই অক্ষম নয়। বুলবুলভাজায় বাছাই করা সম্পাদিত লেখা প্রকাশিত হয়। এখানে লেখা দিতে হলে লেখাটি ইমেইল করুন, বা, গুরুচন্ডা৯ ব্লগ (হরিদাস পাল) বা অন্য কোথাও লেখা থাকলে সেই ওয়েব ঠিকানা পাঠান (ইমেইল ঠিকানা পাতার নীচে আছে), অনুমোদিত এবং সম্পাদিত হলে লেখা এখানে প্রকাশিত হবে। ... আরও ...
  • হরিদাস পালেরা
  • এটি একটি খোলা পাতা, যাকে আমরা ব্লগ বলে থাকি। গুরুচন্ডালির সম্পাদকমন্ডলীর হস্তক্ষেপ ছাড়াই, স্বীকৃত ব্যবহারকারীরা এখানে নিজের লেখা লিখতে পারেন। সেটি গুরুচন্ডালি সাইটে দেখা যাবে। খুলে ফেলুন আপনার নিজের বাংলা ব্লগ, হয়ে উঠুন একমেবাদ্বিতীয়ম হরিদাস পাল, এ সুযোগ পাবেন না আর, দেখে যান নিজের চোখে...... আরও ...
  • টইপত্তর
  • নতুন কোনো বই পড়ছেন? সদ্য দেখা কোনো সিনেমা নিয়ে আলোচনার জায়গা খুঁজছেন? নতুন কোনো অ্যালবাম কানে লেগে আছে এখনও? সবাইকে জানান। এখনই। ভালো লাগলে হাত খুলে প্রশংসা করুন। খারাপ লাগলে চুটিয়ে গাল দিন। জ্ঞানের কথা বলার হলে গুরুগম্ভীর প্রবন্ধ ফাঁদুন। হাসুন কাঁদুন তক্কো করুন। স্রেফ এই কারণেই এই সাইটে আছে আমাদের বিভাগ টইপত্তর। ... আরও ...
  • ভাটিয়া৯
  • যে যা খুশি লিখবেন৷ লিখবেন এবং পোস্ট করবেন৷ তৎক্ষণাৎ তা উঠে যাবে এই পাতায়৷ এখানে এডিটিং এর রক্তচক্ষু নেই, সেন্সরশিপের ঝামেলা নেই৷ এখানে কোনো ভান নেই, সাজিয়ে গুছিয়ে লেখা তৈরি করার কোনো ঝকমারি নেই৷ সাজানো বাগান নয়, আসুন তৈরি করি ফুল ফল ও বুনো আগাছায় ভরে থাকা এক নিজস্ব চারণভূমি৷ আসুন, গড়ে তুলি এক আড়ালহীন কমিউনিটি ... আরও ...
গুরুচণ্ডা৯-র সম্পাদিত বিভাগের যে কোনো লেখা অথবা লেখার অংশবিশেষ অন্যত্র প্রকাশ করার আগে গুরুচণ্ডা৯-র লিখিত অনুমতি নেওয়া আবশ্যক। অসম্পাদিত বিভাগের লেখা প্রকাশের সময় গুরুতে প্রকাশের উল্লেখ আমরা পারস্পরিক সৌজন্যের প্রকাশ হিসেবে অনুরোধ করি। যোগাযোগ করুন, লেখা পাঠান এই ঠিকানায় : guruchandali@gmail.com ।


মে ১৩, ২০১৪ থেকে সাইটটি বার পঠিত
পড়েই ক্ষান্ত দেবেন না। ঝপাঝপ প্রতিক্রিয়া দিন।