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

  • টুরিং মেশিন আর কম্পিউটারের সীমা

    albert banerjee লেখকের গ্রাহক হোন
    ১৬ ফেব্রুয়ারি ২০২৬ | ৩৮ বার পঠিত
  • (0) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
    শিক্ষা আর রাজার অমীমাংসিত প্রশ্ন

    পূর্ব অধ্যায়ে আমরা কনটেক্সট-ফ্রি ভাষা আর পুশডাউন অটোমেটন নিয়ে কথা বলেছিলাম। রাজা কাকের কাছ থেকে অনেক কিছু শিখেছেন। তিনি এখন ডিএফএ, এনএফএ, রেগুলার এক্সপ্রেশন, পিডিএ সবই জানেন। কিন্তু একটা প্রশ্ন সবসময় তাঁর মাথায় ঘুরত। তিনি কাককে জিজ্ঞেস করলেন, কাক, তুমি বলেছিলে পিডিএ-ও সব ভাষা চিনতে পারে না। যেমন aⁿbⁿcⁿ ভাষা চিনতে পারে না। তাহলে কি এমন কোনো যন্ত্র আছে যে সব ভাষা চিনতে পারে?

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

    রাজা বললেন, টুরিং মেশিন? এটা আবার কেমন মেশিন?

    কাক বলল, এর নাম অ্যালান টুরিংয়ের নামে। তিনি একজন ব্রিটিশ বিজ্ঞানী, যিনি কম্পিউটার বিজ্ঞানের জনকদের একজন। তিনি দেখিয়েছিলেন, একটি খুব সহজ যন্ত্র দিয়েই সব কিছু গণনা করা সম্ভব, যদি তার অসীম স্মৃতি থাকে।

    রাজা বললেন, অসীম স্মৃতি? এটা আবার কীভাবে সম্ভব? জগতে তো সবকিছুই সসীম।

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

    রাজা বললেন, তাহলে টুরিং মেশিনটা কেমন দেখতে?

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

    রাজা বললেন, মানে ডিএফএ-র মতো, কিন্তু টেপ আছে?

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

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

    কাক বলল, ধরুন আপনি চান aⁿbⁿcⁿ ভাষা চিনবেন। মানে প্রথমে n সংখ্যক a, তারপর n সংখ্যক b, তারপর n সংখ্যক c। এটা পিডিএ-র পক্ষে সম্ভব নয়, কারণ স্ট্যাক দিয়ে একসঙ্গে দুটো জিনিসের হিসাব রাখা কঠিন। কিন্তু টুরিং মেশিন পারে।

    টুরিং মেশিন কীভাবে করবে? প্রথমে সে টেপের শুরুতে যাবে। তারপর প্রথম a দেখে সেটাকে X দিয়ে বদলে দেবে। তারপর ডান দিকে যেতে থাকবে, প্রথম b খুঁজবে। b পেলে সেটাকে Y দিয়ে বদলে দেবে। তারপর ডান দিকে যেতে থাকবে, প্রথম c খুঁজবে। c পেলে সেটাকে Z দিয়ে বদলে দেবে। তারপর আবার বাঁয়ে ফিরে যাবে শুরুতে। আবার প্রথম a খুঁজবে। এভাবে চলতে থাকবে। যখন সব a, b, c শেষ হয়ে যাবে, আর টেপে শুধু X, Y, Z থাকবে, তখন মেশিন থামবে আর বলবে হ্যাঁ।

    এভাবে টুরিং মেশিন aⁿbⁿcⁿ ভাষা চিনতে পারে।

    রাজা বললেন, তাহলে বুঝলাম, টুরিং মেশিন অনেক শক্তিশালী। কিন্তু এর কি কোনো সীমা নেই? সব ভাষাই কি টুরিং মেশিন চিনতে পারে?

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

    রাজা অবাক হয়ে বললেন, টুরিং মেশিনও পারে না? সেটা আবার কী ধরনের ভাষা?

    কাক বলল, এর সবচেয়ে বিখ্যাত উদাহরণ হলো হাল্টিং প্রবলেম। এই সমস্যাটি হলো: একটি প্রোগ্রাম দেওয়া আছে, আর তার ইনপুট দেওয়া আছে। বলতে হবে, প্রোগ্রামটি কি এই ইনপুট নিয়ে শেষ পর্যন্ত থামবে, নাকি চিরকাল চলতে থাকবে?

    রাজা বললেন, এটা তো সহজ মনে হচ্ছে। প্রোগ্রামটা চালিয়ে দেখলেই তো জানা যায়। যদি থামে, তাহলে বলব থামে। যদি না থামে, তাহলে বলব না থামে।

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

    রাজা বললেন, তাহলে কি এর কোনো সমাধান নেই?

    কাক বলল, অ্যালান টুরিং প্রমাণ করেছেন, এর কোনো সাধারণ সমাধান নেই। অর্থাৎ এমন কোনো অ্যালগরিদম নেই, যা যেকোনো প্রোগ্রামের জন্য বলে দিতে পারে সেটা থামবে কি না। এটা অমীমাংসিত।

    রাজা বললেন, এটা তো অবাক করা কথা। মানে কিছু সমস্যা আছে যা কখনো সমাধান করা যাবে না?

    কাক বলল, হ্যাঁ। এটাই কম্পিউটার বিজ্ঞানের সবচেয়ে মৌলিক সীমা। কিছু সমস্যা আছে যা কখনো অ্যালগরিদম দিয়ে সমাধান করা সম্ভব নয়।

    এবার আমরা একটু গভীরে যাই। টুরিং মেশিনকে আমরা আধুনিক কম্পিউটারের একটি আদর্শ রূপ বলে ভাবতে পারি। আধুনিক কম্পিউটার যা করতে পারে, টুরিং মেশিনও তা পারে। আর টুরিং মেশিন যা করতে পারে না, আধুনিক কম্পিউটারও তা পারে না।

    তাই টুরিং মেশিনের সীমা আসলে কম্পিউটারের সীমা।

    এখন প্রশ্ন হলো, টুরিং মেশিন দিয়ে কী কী করা যায়? প্রায় সব কিছুই করা যায়। যেমন গাণিতিক সমস্যা সমাধান, ডাটা প্রসেসিং, সিমুলেশন, সব কিছুই করা যায়। কিন্তু কিছু সমস্যা আছে যেগুলো করা যায় না।

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

    এ কারণে সফটওয়্যার টেস্টিং এত কঠিন। আমরা কখনো নিশ্চিত হতে পারি না যে কোনো প্রোগ্রামে কোনো বাগ নেই। শুধু বলতে পারি, আমাদের টেস্টগুলোতে তো বাগ পাইনি।

    এবার আমরা আরেকটি গুরুত্বপূর্ণ বিষয় দেখি। টুরিং মেশিনের সঙ্গে আমাদের আগের সব অটোমেটনের সম্পর্ক কী?

    প্রথমে ছিল ডিএফএ। সেটা সবচেয়ে দুর্বল। তারপর এনএফএ, সমান শক্তির। তারপর পিডিএ, আরও শক্তিশালী। তারপর টুরিং মেশিন, সবচেয়ে শক্তিশালী।

    ডিএফএ যা পারে, পিডিএ-ও তা পারে। পিডিএ যা পারে, টুরিং মেশিনও তা পারে। কিন্তু উল্টোটা সত্যি নয়। টুরিং মেশিন যা পারে, পিডিএ তা নাও পারতে পারে। পিডিএ যা পারে, ডিএফএ তা নাও পারতে পারে।

    এভাবে এদের একটা শ্রেণিবিন্যাস আছে। একে বলে চমস্কি হায়ারার্কি। নোয়াম চমস্কি নামের একজন ভাষাবিজ্ঞানী এই শ্রেণিবিন্যাস তৈরি করেছিলেন।

    চমস্কি হায়ারার্কিতে চারটি স্তর আছে। স্তর ৩ হলো রেগুলার ভাষা, ডিএফএ আর এনএফএ দিয়ে চেনানো যায়। স্তর ২ হলো কনটেক্সট-ফ্রি ভাষা, পিডিএ দিয়ে চেনানো যায়। স্তর ১ হলো কনটেক্সট-সেনসিটিভ ভাষা, লিনিয়ার বাউন্ডেড অটোমেটন দিয়ে চেনানো যায়। আর স্তর ০ হলো রিকার্সিভলি এনুমারেবল ভাষা, টুরিং মেশিন দিয়ে চেনানো যায়।

    প্রতিটি পরবর্তী স্তর আগের স্তরের চেয়ে বড়। মানে সব রেগুলার ভাষাই কনটেক্সট-ফ্রি, সব কনটেক্সট-ফ্রি ভাষাই কনটেক্সট-সেনসিটিভ, সব কনটেক্সট-সেনসিটিভ ভাষাই রিকার্সিভলি এনুমারেবল।

    কিন্তু সব রিকার্সিভলি এনুমারেবল ভাষা কি টুরিং মেশিন চিনতে পারে? হ্যাঁ, পারে। কিন্তু টুরিং মেশিন চিরকাল চলতে পারে, থামতে পারে না। আমরা চাই মেশিন সবসময় থামুক। যে সব ভাষার জন্য টুরিং মেশিন সবসময় থামে, তাদের বলে রিকার্সিভ ভাষা। এরা রিকার্সিভলি এনুমারেবল ভাষার একটি উপসেট।

    এখন আমরা বুঝতে পারছি, ভাষার জগৎ অনেক বড়। আর এর সীমা আছে।

    এবার আমরা বাস্তব জীবনে ফিরে আসি। টুরিং মেশিনের ধারণা কোথায় কাজে লাগে?

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

    দ্বিতীয়ত, সফটওয়্যার ভেরিফিকেশনে। আমরা চাই কোনো প্রোগ্রাম সবসময় ঠিকভাবে কাজ করবে। কিন্তু সাধারণভাবে সেটা প্রমাণ করা সম্ভব নয়। তাই আমরা কিছু নির্দিষ্ট প্রোপার্টি চেক করি।

    তৃতীয়ত, কৃত্রিম বুদ্ধিমত্তায়। এআই-এরও সীমা আছে। কিছু সমস্যা আছে যা এআই-ও সমাধান করতে পারে না।

    চতুর্থত, ক্রিপ্টোগ্রাফিতে। কিছু গাণিতিক সমস্যা এত কঠিন যে সেগুলো সমাধান করতে বহু বছর লেগে যাবে। সেই কঠিনতার ওপর ভিত্তি করেই ক্রিপ্টোগ্রাফি তৈরি।

    পঞ্চমত, দর্শনে। টুরিং মেশিনের সীমা আমাদের বলে, মানুষের চিন্তারও কি সীমা আছে? আমরা কি সব কিছু জানতে পারব? এই প্রশ্ন দার্শনিকদের জন্য।

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

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

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

    রাজা বললেন, তাহলে আমাদের কাজ হলো সেই সব সমস্যা চেনা যার সমাধান সম্ভব, আর সেগুলোর সমাধান করা।

    কাক বলল, ঠিক তাই। আর এই জ্ঞানই আপনাকে একজন ভালো ইঞ্জিনিয়ার করে তুলবে।

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

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

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

    তিনি বুঝলেন, অটোমেটা তত্ত্ব শুধু পরীক্ষার জন্য নয়, বাস্তব জগতের জন্য।

    এখন আমরা অধ্যায় ৬ শেষ করি এই জেনে যে:

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

    এই পর্যন্ত আমরা অটোমেটা তত্ত্বের পুরো যাত্রা শেষ করলাম। আমরা শুরু করেছিলাম বাইনারি বনের ছোট্ট একটি ডিএফএ দিয়ে। শেষ করলাম টুরিং মেশিন আর অমীমাংসিত সমস্যার কথা বলে।

    এই যাত্রায় আমরা শিখলাম:

    প্রথম অধ্যায়ে শিখলাম বর্ণমালা, স্ট্রিং, ভাষা আর অটোমেটনের মৌলিক ধারণা।
    দ্বিতীয় অধ্যায়ে শিখলাম ডিএফএ, তার গঠন আর বাস্তবায়ন।
    তৃতীয় অধ্যায়ে শিখলাম এনএফএ আর ডিএফএ-র সমতুল্যতা।
    চতুর্থ অধ্যায়ে শিখলাম রেগুলার এক্সপ্রেশন আর পাম্পিং লেমা।
    পঞ্চম অধ্যায়ে শিখলাম কনটেক্সট-ফ্রি ভাষা, পিডিএ আর গ্রামার।
    ষষ্ঠ অধ্যায়ে শিখলাম টুরিং মেশিন আর কম্পিউটারের সীমা।

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

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

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

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

    ঠিক তখনই তাঁর মনে পড়ল কাকের শেষ কথাটি। কাক বলেছিল, "চমস্কি হায়ারার্কি"। রাজা জানতে চাইলেন, সেটা আবার কী?

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

    গল্পটা শুরু করি আবার বাইনারি বন থেকে। রাজা তাঁর প্রজাদের জন্য বিভিন্ন ভাষা বানাচ্ছিলেন। কিছু ভাষা খুব সহজ, যেমন শেষে ০১ থাকবে। কিছু ভাষা একটু কঠিন, যেমন সমান সংখ্যক ০ আর ১। কিছু ভাষা আরও কঠিন, যেমন aⁿbⁿcⁿ। আর কিছু ভাষা এত কঠিন যে তার সমাধানই নেই।

    রাজা বুঝলেন, এই ভাষাগুলো আলাদা আলাদা স্তরের। আর এই স্তরগুলোই হলো চমস্কি হায়ারার্কি।

    এখন আমরা স্তরগুলো একে একে দেখব।

    প্রথম স্তর: টাইপ ৩ - রেগুলার ভাষা

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

    এই স্তরের ভাষাগুলোতে কোনো গণনার দরকার হয় না। শুধু প্যাটার্ন মেলালেই চলে। যেমন শেষে ০১ থাকবে, বা শুরুতে ১ থাকবে, বা মাঝে ১১১ নেই, এরকম।

    এই স্তরের ব্যাকরণকে বলে রেগুলার গ্রামার। এর নিয়মগুলো খুব কঠোর। যেমন A → aB বা A → a এরকম হতে পারে, কিন্তু A → aBc এরকম হতে পারে না।

    আমাদের বনের উদাহরণ: শেষে ০১ থাকবে এমন ভাষা। এর রেগুলার এক্সপ্রেশন (০|১)*০১।

    এই স্তরের অটোমেটন: ডিএফএ, এনএফএ।

    দ্বিতীয় স্তর: টাইপ ২ - কনটেক্সট-ফ্রি ভাষা

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

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

    এই স্তরের ব্যাকরণের নিয়মগুলো একটু শিথিল। যেমন S → ০S১ বা S → SS লেখা যায়। কিন্তু এখনও কিছু নিয়ম মেনে চলতে হয়। যেমন বাঁ পাশে সবসময় একটা মাত্র নন-টার্মিনাল থাকবে।

    আমাদের বনের উদাহরণ: সমান সংখ্যক ০ আর ১, যে কোনো ক্রমে। এর গ্রামার S → ০S১ | ১S০ | SS | ε।

    এই স্তরের অটোমেটন: পুশডাউন অটোমেটন।

    তৃতীয় স্তর: টাইপ ১ - কনটেক্সট-সেনসিটিভ ভাষা

    এই স্তরটি আরও বড়। এখানে সেই সব ভাষা আসে যাদের লিনিয়ার বাউন্ডেড অটোমেটন দিয়ে চেনানো যায়। লিনিয়ার বাউন্ডেড অটোমেটন হলো টুরিং মেশিনের একটি বিশেষ রূপ, যার টেপের দৈর্ঘ্য ইনপুটের দৈর্ঘ্যের সমানুপাতিক।

    এই স্তরের ভাষাগুলোতে প্রসঙ্গ দেখতে হয়। যেমন aⁿbⁿcⁿ এই স্তরের একটি ভাষা। এখানে a, b, c-এর সংখ্যা সমান হতে হবে, আর সেগুলো নির্দিষ্ট ক্রমে সাজানো থাকতে হবে।

    এই স্তরের ব্যাকরণের নিয়মগুলো আরও শিথিল। এখানে α → β এরকম নিয়ম লেখা যায়, যেখানে α আর β-এর দৈর্ঘ্যের একটা সম্পর্ক থাকে। সাধারণত |α| ≤ |β| হতে হয়।

    আমাদের বনের উদাহরণ: aⁿbⁿcⁿ, যেখানে প্রথমে n সংখ্যক a, তারপর n সংখ্যক b, তারপর n সংখ্যক c।

    এই স্তরের অটোমেটন: লিনিয়ার বাউন্ডেড অটোমেটন।

    চতুর্থ স্তর: টাইপ ০ - রিকার্সিভলি এনুমারেবল ভাষা

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

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

    এই স্তরের ব্যাকরণের কোনো সীমা নেই। যে কোনো নিয়ম লেখা যায়। α → β, যেখানে α আর β যেকোনো কিছু হতে পারে, কিন্তু α ফাঁকা হতে পারে না।

    আমাদের বনের উদাহরণ: হাল্টিং প্রবলেমের ভাষা। কিন্তু এটা আসলে এই স্তরেরও বাইরে, কারণ টুরিং মেশিনও এটা চিনতে পারে না।

    এই স্তরের অটোমেটন: টুরিং মেশিন।

    স্তরগুলোর সম্পর্ক

    এখন প্রশ্ন হলো, এই স্তরগুলোর মধ্যে সম্পর্ক কী?

    প্রথমত, প্রতিটি নিচের স্তর উপরের স্তরের একটি উপসেট। মানে:

    টাইপ ৩ ⊂ টাইপ ২ ⊂ টাইপ ১ ⊂ টাইপ ০

    অর্থাৎ সব রেগুলার ভাষাই কনটেক্সট-ফ্রি। সব কনটেক্সট-ফ্রি ভাষাই কনটেক্সট-সেনসিটিভ। সব কনটেক্সট-সেনসিটিভ ভাষাই রিকার্সিভলি এনুমারেবল।

    কিন্তু উল্টোটা সত্যি নয়। কিছু কনটেক্সট-ফ্রি ভাষা আছে যারা রেগুলার নয়, যেমন aⁿbⁿ। কিছু কনটেক্সট-সেনসিটিভ ভাষা আছে যারা কনটেক্সট-ফ্রি নয়, যেমন aⁿbⁿcⁿ। কিছু রিকার্সিভলি এনুমারেবল ভাষা আছে যারা কনটেক্সট-সেনসিটিভ নয়।

    আর কিছু ভাষা আছে যারা রিকার্সিভলি এনুমারেবল-ও নয়। এরা চমস্কি হায়ারার্কির বাইরে।

    আরেকটু সহজ করে বলা

    ধরুন, আপনার একটা বাগান আছে। সেখানে চার ধরনের গাছ আছে।

    প্রথম ধরনের গাছ খুব ছোট, সহজে বাড়ে। এরা রেগুলার ভাষা।

    দ্বিতীয় ধরনের গাছ একটু বড়, একটু যত্ন লাগে। এরা কনটেক্সট-ফ্রি ভাষা।

    তৃতীয় ধরনের গাছ আরও বড়, অনেক যত্ন লাগে। এরা কনটেক্সট-সেনসিটিভ ভাষা।

    চতুর্থ ধরনের গাছ অনেক বড়, কিন্তু কোনো নিয়ম নেই, যে কোনোভাবে বাড়তে পারে। এরা রিকার্সিভলি এনুমারেবল ভাষা।

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

    বাস্তব উদাহরণ

    এবার আমরা বাস্তব জীবনের কিছু উদাহরণ দেখি।

    রেগুলার ভাষা: ইমেল ঠিকানা, ফোন নম্বর, পিন কোড, ওয়েব ঠিকানা। এগুলো রেগুলার এক্সপ্রেশন দিয়ে চেনানো যায়।

    কনটেক্সট-ফ্রি ভাষা: প্রোগ্রামিং ভাষার সিনট্যাক্স, HTML ট্যাগ, গাণিতিক এক্সপ্রেশন। এগুলো কনটেক্সট-ফ্রি গ্রামার দিয়ে বর্ণনা করা যায়।

    কনটেক্সট-সেনসিটিভ ভাষা: কিছু প্রোগ্রামিং ভাষার সেমান্টিক চেক, যেমন ভেরিয়েবল ডিক্লেয়ার করার আগে ব্যবহার করা যাবে কি না। এটা সাধারণত কম্পাইলারের পরবর্তী ধাপে চেক করা হয়।

    রিকার্সিভলি এনুমারেবল ভাষা: যেকোনো প্রোগ্রামের আউটপুট। কিন্তু সব প্রোগ্রাম থামে না, তাই সব আউটপুট পাওয়া যায় না।

    চমস্কি হায়ারার্কির গুরুত্ব

    এত শ্রেণিবিন্যাস করে লাভ কী? লাভ অনেক।

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

    দ্বিতীয়ত, এটি আমাদের বলে, কোনো সমস্যার সমাধান সম্ভব কি না। যদি কোনো ভাষা টাইপ ০-ও না হয়, তাহলে তার জন্য কোনো অ্যালগরিদম নেই। যেমন হাল্টিং প্রবলেম।

    তৃতীয়ত, এটি ভাষাবিজ্ঞানীদের ভাষা বুঝতে সাহায্য করে। মানুষের ভাষা কোন স্তরের, সেটা নিয়ে গবেষণা হয়।

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

    রাজা চমস্কি হায়ারার্কি বুঝতে পেরে খুব খুশি হলেন। তিনি এখন জানেন, তাঁর বনের সব ভাষা কোন স্তরে পড়ে। তিনি বুঝলেন, কেন কিছু ভাষা এত সহজ, আর কিছু এত কঠিন।

    তিনি তাঁর প্রজাদের জন্য একটি চার্ট বানালেন:

    | স্তর | নাম | অটোমেটন | উদাহরণ |
    |------|------|----------|--------|
    | টাইপ ৩ | রেগুলার | ডিএফএ, এনএফএ | শেষে ০১ |
    | টাইপ ২ | কনটেক্সট-ফ্রি | পিডিএ | সমান ০ আর ১ |
    | টাইপ ১ | কনটেক্সট-সেনসিটিভ | এলবিএ | aⁿbⁿcⁿ |
    | টাইপ ০ | রিকার্সিভলি এনুমারেবল | টুরিং মেশিন | যে কোনো প্রোগ্রাম |

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

    রাজা ঠিক করলেন, এবার তিনি একটি লিনিয়ার বাউন্ডেড অটোমেটন বানাবেন।
    পুনঃপ্রকাশ সম্পর্কিত নীতিঃ এই লেখাটি ছাপা, ডিজিটাল, দৃশ্য, শ্রাব্য, বা অন্য যেকোনো মাধ্যমে আংশিক বা সম্পূর্ণ ভাবে প্রতিলিপিকরণ বা অন্যত্র প্রকাশের জন্য গুরুচণ্ডা৯র অনুমতি বাধ্যতামূলক। লেখক চাইলে অন্যত্র প্রকাশ করতে পারেন, সেক্ষেত্রে গুরুচণ্ডা৯র উল্লেখ প্রত্যাশিত।
    (0) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
  • মতামত দিন
  • বিষয়বস্তু*:
এই সাইটটি বার পঠিত
  • কি, কেন, ইত্যাদি
  • বাজার অর্থনীতির ধরাবাঁধা খাদ্য-খাদক সম্পর্কের বাইরে বেরিয়ে এসে এমন এক আস্তানা বানাব আমরা, যেখানে ক্রমশ: মুছে যাবে লেখক ও পাঠকের বিস্তীর্ণ ব্যবধান। পাঠকই লেখক হবে, মিডিয়ার জগতে থাকবেনা কোন ব্যকরণশিক্ষক, ক্লাসরুমে থাকবেনা মিডিয়ার মাস্টারমশাইয়ের জন্য কোন বিশেষ প্ল্যাটফর্ম। এসব আদৌ হবে কিনা, গুরুচণ্ডালি টিকবে কিনা, সে পরের কথা, কিন্তু দু পা ফেলে দেখতে দোষ কী? ... আরও ...
  • আমাদের কথা
  • আপনি কি কম্পিউটার স্যাভি? সারাদিন মেশিনের সামনে বসে থেকে আপনার ঘাড়ে পিঠে কি স্পন্ডেলাইটিস আর চোখে পুরু অ্যান্টিগ্লেয়ার হাইপাওয়ার চশমা? এন্টার মেরে মেরে ডান হাতের কড়ি আঙুলে কি কড়া পড়ে গেছে? আপনি কি অন্তর্জালের গোলকধাঁধায় পথ হারাইয়াছেন? সাইট থেকে সাইটান্তরে বাঁদরলাফ দিয়ে দিয়ে আপনি কি ক্লান্ত? বিরাট অঙ্কের টেলিফোন বিল কি জীবন থেকে সব সুখ কেড়ে নিচ্ছে? আপনার দুশ্‌চিন্তার দিন শেষ হল। ... আরও ...
  • বুলবুলভাজা
  • এ হল ক্ষমতাহীনের মিডিয়া। গাঁয়ে মানেনা আপনি মোড়ল যখন নিজের ঢাক নিজে পেটায়, তখন তাকেই বলে হরিদাস পালের বুলবুলভাজা। পড়তে থাকুন রোজরোজ। দু-পয়সা দিতে পারেন আপনিও, কারণ ক্ষমতাহীন মানেই অক্ষম নয়। বুলবুলভাজায় বাছাই করা সম্পাদিত লেখা প্রকাশিত হয়। এখানে লেখা দিতে হলে লেখাটি ইমেইল করুন, বা, গুরুচন্ডা৯ ব্লগ (হরিদাস পাল) বা অন্য কোথাও লেখা থাকলে সেই ওয়েব ঠিকানা পাঠান (ইমেইল ঠিকানা পাতার নীচে আছে), অনুমোদিত এবং সম্পাদিত হলে লেখা এখানে প্রকাশিত হবে। ... আরও ...
  • হরিদাস পালেরা
  • এটি একটি খোলা পাতা, যাকে আমরা ব্লগ বলে থাকি। গুরুচন্ডালির সম্পাদকমন্ডলীর হস্তক্ষেপ ছাড়াই, স্বীকৃত ব্যবহারকারীরা এখানে নিজের লেখা লিখতে পারেন। সেটি গুরুচন্ডালি সাইটে দেখা যাবে। খুলে ফেলুন আপনার নিজের বাংলা ব্লগ, হয়ে উঠুন একমেবাদ্বিতীয়ম হরিদাস পাল, এ সুযোগ পাবেন না আর, দেখে যান নিজের চোখে...... আরও ...
  • টইপত্তর
  • নতুন কোনো বই পড়ছেন? সদ্য দেখা কোনো সিনেমা নিয়ে আলোচনার জায়গা খুঁজছেন? নতুন কোনো অ্যালবাম কানে লেগে আছে এখনও? সবাইকে জানান। এখনই। ভালো লাগলে হাত খুলে প্রশংসা করুন। খারাপ লাগলে চুটিয়ে গাল দিন। জ্ঞানের কথা বলার হলে গুরুগম্ভীর প্রবন্ধ ফাঁদুন। হাসুন কাঁদুন তক্কো করুন। স্রেফ এই কারণেই এই সাইটে আছে আমাদের বিভাগ টইপত্তর। ... আরও ...
  • ভাটিয়া৯
  • যে যা খুশি লিখবেন৷ লিখবেন এবং পোস্ট করবেন৷ তৎক্ষণাৎ তা উঠে যাবে এই পাতায়৷ এখানে এডিটিং এর রক্তচক্ষু নেই, সেন্সরশিপের ঝামেলা নেই৷ এখানে কোনো ভান নেই, সাজিয়ে গুছিয়ে লেখা তৈরি করার কোনো ঝকমারি নেই৷ সাজানো বাগান নয়, আসুন তৈরি করি ফুল ফল ও বুনো আগাছায় ভরে থাকা এক নিজস্ব চারণভূমি৷ আসুন, গড়ে তুলি এক আড়ালহীন কমিউনিটি ... আরও ...
গুরুচণ্ডা৯-র সম্পাদিত বিভাগের যে কোনো লেখা অথবা লেখার অংশবিশেষ অন্যত্র প্রকাশ করার আগে গুরুচণ্ডা৯-র লিখিত অনুমতি নেওয়া আবশ্যক। অসম্পাদিত বিভাগের লেখা প্রকাশের সময় গুরুতে প্রকাশের উল্লেখ আমরা পারস্পরিক সৌজন্যের প্রকাশ হিসেবে অনুরোধ করি। যোগাযোগ করুন, লেখা পাঠান এই ঠিকানায় : guruchandali@gmail.com ।


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