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

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

    albert banerjee লেখকের গ্রাহক হোন
    ১৫ ফেব্রুয়ারি ২০২৬ | ৩৪ বার পঠিত
  • 00 | 1 | 02 | 003
    রোবটের দ্বিধা আর জাদুর পথ

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

    কিন্তু একদিন বনে এক জাদুকর এল। জাদুকর রাজাকে বলল, রাজা, আপনার রোবটটি ভালো, কিন্তু আমি তাকে আরও শক্তিশালী করতে পারি। আমি তাকে জাদু দিতে পারি, যাতে সে একই সময়ে একাধিক পথে যেতে পারে।

    রাজা আশ্চর্য হয়ে বললেন, একই সময়ে একাধিক পথে যাওয়া? এটা কীভাবে সম্ভব? একটা রোবট তো একই সময়ে একটা জায়গাতেই থাকতে পারে।

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

    এই জাদুকর যে রোবটের কথা বলল, সেটাই হলো ননডিটারমিনিস্টিক ফিনাইট অটোমেটন, বা সংক্ষেপে এনএফএ।

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

    এটা শুনে রাজা বললেন, কিন্তু এত পথে গিয়ে সে তো বিভ্রান্ত হবে। শেষমেশ সে কীভাবে সিদ্ধান্ত নেবে কোনটা ঠিক?

    জাদুকর বললেন, রাজা, সে সব পথেই যায়। কল্পনা করুন, আপনার রোবটের অনেকগুলো কপি তৈরি হয়ে যায়। প্রতিটি কপি একটা করে পথে যায়। শেষে যদি কোনো একটা কপিও স্বীকৃত অবস্থায় পৌঁছায়, তাহলে আমরা বলব স্ট্রিংটি স্বীকৃত।

    এটা শুনে রাজা মুগ্ধ হলেন। তিনি বললেন, তাহলে কি এনএফএ ডিএফএ-র চেয়ে শক্তিশালী?

    জাদুকর বললেন, না রাজা, শক্তিশালী নয়, কিন্তু ব্যবহারে সহজ। ডিএফএ যা পারে, এনএফএ-ও তা পারে। আর এনএফএ যা পারে, ডিএফএ-ও তা পারে। এরা সমান শক্তির। শুধু এনএফএ দিয়ে ভাষা ডিজাইন করা সহজ, কিন্তু বাস্তবায়ন করা কঠিন। ডিএফএ দিয়ে বাস্তবায়ন করা সহজ, কিন্তু ডিজাইন করা কঠিন।

    এবার আমরা একটি উদাহরণ দেখি। রাজা বললেন, আমি একটি ভাষা বানাতে চাই, যেখানে স্ট্রিং-এর শেষের দিক থেকে তৃতীয় অক্ষরটি ১ হবে। যেমন ১০১, ১১০, ০১১, ১১১০১ ইত্যাদি। অর্থাৎ শেষের তিনটি অক্ষরের মধ্যে প্রথমটি ১ হবে।

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

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

    q0 থেকে ১ পড়লে আমরা q1-এ যাই। q1 থেকে যেকোনো ০ বা ১ পড়লে q2-এ যাই। q2 থেকে যেকোনো ০ বা ১ পড়লে q3-এ যাই। q3 স্বীকৃত অবস্থা।

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

    এভাবে একাধিক পথে এগিয়ে গিয়ে শেষ পর্যন্ত যদি কোনো পথ q3-এ পৌঁছায়, তাহলে স্ট্রিং স্বীকৃত।

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

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

    আসলে এটা একটু জটিল। সহজ উপায় হলো, q0 থেকে ০ বা ১ পড়লে q0-তেই থাকি। আর ১ পড়লে আমরা q1-এ যাই, যা স্বীকৃত অবস্থা। কিন্তু এটা তো ডিএফএ-ও করতে পারে। তাহলে এপসাইলনের দরকার কোথায়?

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

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

    কিন্তু এনএফএ-কে ডিএফএ-তে রূপান্তর করার পদ্ধতিটা কী? সেটার নাম সাবসেট কনস্ট্রাকশন। এই পদ্ধতিতে আমরা এনএফএ-র একাধিক অবস্থাকে একসাথে নিয়ে ডিএফএ-র একটি অবস্থা বানাই। যেমন এনএফএ-র যদি তিনটি অবস্থা থাকে q0, q1, q2, তাহলে ডিএফএ-র একটি অবস্থা হতে পারে {q0, q1} মানে এনএফএ একই সময়ে q0 আর q1-এ আছে। এভাবে এনএফএ-র সব সম্ভাব্য অবস্থার সেটগুলো ডিএফএ-র অবস্থা হয়।

    এতে ডিএফএ-র অবস্থার সংখ্যা অনেক বেড়ে যেতে পারে। এনএফএ-র যদি nটি অবস্থা থাকে, তাহলে ডিএফএ-র সর্বোচ্চ ২ এর ঘাত n টি অবস্থা হতে পারে। কিন্তু বাস্তবে সবগুলো অবস্থার দরকার হয় না।

    এখন আমরা একটি উদাহরণ দেখি। আগের উদাহরণটাই নিই, যেখানে শেষের দিক থেকে তৃতীয় অক্ষর ১ হবে। সেখানে এনএফএ-র তিনটি অবস্থা ছিল। এখন সেটাকে ডিএফএ-তে রূপান্তর করি।

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

    তাহলে ডিএফএ-র শুরু অবস্থা হবে {q0}। এখন {q0} থেকে ০ পড়লে আমরা {q0}-তে যাই। ১ পড়লে আমরা {q0, q1}-এ যাই।

    এবার {q0, q1} থেকে ০ পড়লে কী হবে? q0 থেকে ০ পড়লে q0, q1 থেকে ০ পড়লে q2। তাহলে আমরা পাই {q0, q2}। আবার {q0, q1} থেকে ১ পড়লে q0 থেকে q0 ও q1, আর q1 থেকে q2। তাহলে পাই {q0, q1, q2}।

    এভাবে চলতে থাকে। শেষ পর্যন্ত আমরা সবগুলো সম্ভাব্য সেট পাব। তারপর দেখব কোন সেটে q3 আছে, সেগুলো হবে স্বীকৃত অবস্থা।

    এভাবে এনএফএ-কে ডিএফএ-তে রূপান্তর করা যায়।

    এখন প্রশ্ন হলো, এনএফএ দিয়ে কী লাভ? ডিএফএ তো আছে, তাহলে এনএফএ কেন দরকার?

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

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

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

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

    কিন্তু বাস্তব জীবনে আমরা এনএফএ সরাসরি ব্যবহার করি না, কারণ বাস্তবায়ন করা কঠিন। কম্পিউটার তো আসলে ডিটারমিনিস্টিক মেশিন। তাই আমরা এনএফএ ডিজাইন করি, তারপর সেটাকে ডিএফএ-তে রূপান্তর করি, তারপর সেই ডিএফএ বাস্তবায়ন করি।

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

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

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

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

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

    তাই এনএফএ সবসময় সুবিধাজনক নয়, কিন্তু অনেক সময় সুবিধাজনক।

    এখন আমরা আরেকটি গুরুত্বপূর্ণ বিষয় দেখি। এনএফএ আর রেগুলার এক্সপ্রেশনের মধ্যে সম্পর্ক কী? রেগুলার এক্সপ্রেশন হলো একটি ভাষা বর্ণনা করার উপায়। যেমন a*b মানে যেকোনো সংখ্যক a এরপর একটি b। এই রেগুলার এক্সপ্রেশনকে এনএফএ-তে রূপান্তর করা যায়। আবার এনএফএ থেকে রেগুলার এক্সপ্রেশনও বের করা যায়। এরা সমতুল্য।

    এ কারণেই রেগুলার এক্সপ্রেশন ইঞ্জিন এনএফএ ব্যবহার করে। তুমি যখন a*b লেখো, ইঞ্জিন সেটাকে এনএফএ-তে রূপান্তর করে, তারপর সিমুলেট করে।

    এখন আমরা বুঝতে পারছি, এনএফএ শুধু একটি তত্ত্ব নয়, বাস্তব জীবনের একটি গুরুত্বপূর্ণ হাতিয়ার।

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

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

    তাই এনএফএ সব সমস্যার সমাধান নয়, কিন্তু অনেক সমস্যার সমাধান সহজ করে।

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

    তবে তুমি যদি নিজে একটি রেগুলার এক্সপ্রেশন ইঞ্জিন বানাতে চাও, তাহলে তোমাকে এনএফএ বুঝতেই হবে। থম্পসন কনস্ট্রাকশন[১] শিখতে হবে, আর সেটা সিমুলেট করার পদ্ধতি জানতে হবে।

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

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

    এই জ্ঞান রাজাকে অনেক সাহায্য করল। তিনি এখন জানেন, কোন ভাষা সম্ভব আর কোনটা অসম্ভব।

    এখন আমরা অধ্যায় ৩ শেষ করি। এ অধ্যায়ে আমরা শিখলাম:

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

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

    পরবর্তী অধ্যায়ে আমরা রেগুলার এক্সপ্রেশন নিয়ে বিস্তারিত আলোচনা করব।
    [১]
    থম্পসন কনস্ট্রাকশন
    জাদুকরের গুপ্ত বিদ্যা

    আমরা জাদুকরের কথা বলেছিলাম, যে রাজাকে এনএফএ বানিয়ে দিল। কিন্তু সেই এনএফএ বানানোর পদ্ধতিটা আসলে কী ছিল? সেটাই এখন বলব। এই পদ্ধতির নাম থম্পসন কনস্ট্রাকশন। এর জনক কেন থম্পসন, যিনি ইউনিক্সেরও অন্যতম নির্মাতা।

    গল্পটা শুরু করি সেখান থেকেই। রাজা একদিন জাদুকরকে ডেকে বললেন, জাদুকর, তুমি তো বললে এনএফএ দিয়ে সব রেগুলার এক্সপ্রেশন বানানো যায়। কিন্তু আমি নিজে যখন একটা রেগুলার এক্সপ্রেশন দেখি, যেমন (০|১)*০১, তখন আমার মাথায় কোনো এনএফএ আসে না। তুমি কীভাবে বানাও?

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

    রাজা বললেন, বুঝিয়ে বলো।

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

    আর যদি ফাঁকা থাকে, মানে ε, তাহলেও দুটি ঘর, কিন্তু তীরের গায়ে কিছু লেখা নেই। ফাঁকা তীর। শুরু ঘর থেকেই সরাসরি স্বীকৃত ঘরে চলে যাওয়া যায়।

    এবার একটু জটিল নিয়ম। ধরা যাক, আপনার কাছে দুটি এক্সপ্রেশন s আর t আছে। আপনি চান s|t, মানে s অথবা t। তাহলে কী করবেন? প্রথমে s আর t-এর জন্য আলাদা এনএফএ বানান। তারপর একটি নতুন শুরু ঘর বানান। সেই শুরু ঘর থেকে দুটি ফাঁকা তীর দিন। একটি যাবে s-এর শুরু ঘরে, আরেকটি যাবে t-এর শুরু ঘরে। তারপর s-এর স্বীকৃত ঘর থেকে আর t-এর স্বীকৃত ঘর থেকে দুটি ফাঁকা তীর দিন একটি নতুন স্বীকৃত ঘরে। ব্যাস, হয়ে গেল s|t-এর এনএফএ।

    এবার ধরা যাক, আপনি চান s তারপর t, মানে st। তখনও প্রথমে s আর t-এর আলাদা এনএফএ বানান। তারপর s-এর স্বীকৃত ঘর থেকে একটি ফাঁকা তীর দিন t-এর শুরু ঘরে। আর s-এর শুরু ঘরটিকেই পুরো জিনিসের শুরু ঘর রাখুন। t-এর স্বীকৃত ঘরটিকেই পুরো জিনিসের স্বীকৃত ঘর রাখুন। হয়ে গেল।

    এবার সবচেয়ে মজার অপারেটর, ক্লিনি স্টার। s* মানে s শূন্য বা তার বেশি বার। এর জন্য কী করবেন? প্রথমে s-এর এনএফএ বানান। তারপর একটি নতুন শুরু ঘর বানান, আর একটি নতুন স্বীকৃত ঘর বানান। নতুন শুরু ঘর থেকে একটি ফাঁকা তীর দিন s-এর শুরু ঘরে, আর আরেকটি ফাঁকা তীর দিন সরাসরি নতুন স্বীকৃত ঘরে। তারপর s-এর স্বীকৃত ঘর থেকে একটি ফাঁকা তীর দিন s-এর শুরু ঘরে, আর আরেকটি ফাঁকা তীর দিন নতুন স্বীকৃত ঘরে। ব্যাস, হয়ে গেল s*।

    রাজা বললেন, এত নিয়ম মনে রাখা তো কঠিন।

    জাদুকর বললেন, রাজা, চারটে নিয়ম মাত্র। বাকিটা হলো এই নিয়মগুলো ব্যবহার করে বড় এক্সপ্রেশন বানানো। যেমন (০|১)*০১ এই এক্সপ্রেশনটি নিন। প্রথমে ০ আর ১-এর জন্য আলাদা এনএফএ বানান। তারপর ০|১ বানান ইউনিয়ন নিয়মে। তারপর সেটার ওপর ক্লিনি স্টার বসান। তারপর ০ আর ১-এর জন্য আলাদা এনএফএ বানান। তারপর স্টারওয়ালা অংশের শেষ ঘর থেকে প্রথম ০-এর শুরু ঘরে ফাঁকা তীর দিন, তারপর প্রথম ০-এর শেষ ঘর থেকে দ্বিতীয় ১-এর শুরু ঘরে ফাঁকা তীর দিন। শেষে দ্বিতীয় ১-এর শেষ ঘরটিকে পুরো জিনিসের স্বীকৃত ঘর বানান।

    এভাবে ধাপে ধাপে এগোলে যেকোনো রেগুলার এক্সপ্রেশনকে এনএফএ-তে রূপান্তর করা যায়।

    রাজা বললেন, কিন্তু এত ফাঁকা তীর দিয়ে কী হবে? এটা কি জটিল হবে না?

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

    রাজা বললেন, সিমুলেট মানে?

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

    রাজা বললেন, বুঝলাম। এখন একটা উদাহরণ দাও।

    জাদুকর বললেন, ধরুন আপনার রেগুলার এক্সপ্রেশন a|b*c। প্রথমে a-র জন্য এনএফএ বানাই। তারপর b-র জন্য এনএফএ বানাই, তারপর তার ওপর ক্লিনি স্টার বসাই। তারপর c-র জন্য এনএফএ বানাই। তারপর b*c অংশটার জন্য কনক্যাটেনেশন করি b* আর c দিয়ে। তারপর a আর b*c অংশটার জন্য ইউনিয়ন করি। শেষ পর্যন্ত একটা বড় এনএফএ পাব। এত বড় যে হাতে আঁকা কঠিন, কিন্তু কম্পিউটার খুব সহজেই বানাতে পারে।

    রাজা বললেন, কিন্তু এই পদ্ধতি কি সব রেগুলার এক্সপ্রেশনের জন্য কাজ করে?

    জাদুকর বললেন, হ্যাঁ, সব রেগুলার এক্সপ্রেশনের জন্য কাজ করে। এমনকি খুব জটিল এক্সপ্রেশন যেমন (০|(১(০১*(০০)*০)*১)*)*-এর জন্যও কাজ করে। এই এক্সপ্রেশনটি দিয়ে বোঝায় ৩ দিয়ে বিভাজ্য সব বাইনারি সংখ্যা। এর জন্য থম্পসন কনস্ট্রাকশন দিয়ে এনএফএ বানানো যায়, কিন্তু সেটা অনেক বড় হবে।

    রাজা বললেন, তাহলে বুঝলাম, থম্পসন কনস্ট্রাকশন হলো একটা রেসিপির মতো। রেসিপিতে বলা আছে, প্রথমে এই উপাদানগুলো আলাদা করো, তারপর এভাবে জুড়ো।

    জাদুকর বললেন, ঠিক তাই। আর এই রেসিপি ফলো করলেই যেকোনো রেগুলার এক্সপ্রেশন থেকে এনএফএ বানানো যায়।

    রাজা বললেন, তাহলে আমি যদি নিজে একটা রেগুলার এক্সপ্রেশন ইঞ্জিন বানাতে চাই, তাহলে এই পদ্ধতি ব্যবহার করব।

    জাদুকর বললেন, হ্যাঁ। আরও মজার কথা হলো, এই পদ্ধতি এতটাই কার্যকর যে পাইথন, পার্ল, জাভাস্ক্রিপ্টের মতো ভাষার রেগুলার এক্সপ্রেশন ইঞ্জিনগুলো থম্পসন কনস্ট্রাকশনেরই ভিন্ন সংস্করণ ব্যবহার করে।

    রাজা বললেন, তাহলে তো এটা খুবই গুরুত্বপূর্ণ।

    জাদুকর বললেন, অবশ্যই। থম্পসন কনস্ট্রাকশন শুধু তত্ত্ব নয়, বাস্তব জগতের একটা শক্তিশালী হাতিয়ার।

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

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

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

    এই পদ্ধতির সময় জটিলতা O(n × m), যেখানে n হলো স্ট্রিং-এর দৈর্ঘ্য, m হলো এনএফএ-র অবস্থার সংখ্যা। যেহেতু m সাধারণত ছোট হয়, তাই এই পদ্ধতি খুব দ্রুত কাজ করে।

    এখন আমরা যদি আমাদের পুরোনো ইমেল রিডারের উদাহরণে ফিরে যাই, তাহলে দেখতে পাব, ইমেল ঠিকানা যাচাই করার জন্য আমরা একটা রেগুলার এক্সপ্রেশন লিখতে পারি। যেমন [a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}। এই এক্সপ্রেশনটাকে থম্পসন কনস্ট্রাকশন দিয়ে এনএফএ-তে রূপান্তর করা যায়। তারপর সেই এনএফএ দিয়ে যেকোনো ইমেল ঠিকানা যাচাই করা যায়।

    এভাবে থম্পসন কনস্ট্রাকশন আমাদের বনের গল্প থেকে বেরিয়ে এসে বাস্তব জগতে পা রাখে।

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

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


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