L ={0(n+m)1m2n | এর জন্য পুশডাউন অটোমেটা তৈরি করুন m, n =0} C++ এ

আমাদের একটি ভাষা "L" দেওয়া হয়েছে এবং কাজটি হল প্রদত্ত ভাষার জন্য একটি পুশডাউন অটোমেটা তৈরি করা যা ব্যাখ্যা করে যে 0 এর ঘটনাগুলি 1 এবং 2 এর সংঘটনের সংযোজন হবে এবং এছাড়াও, 1 এবং 2 এর উপস্থিতি সর্বনিম্ন একটি হবে যা স্ট্রিংটিকে NULLও করতে পারে এবং এটি স্বয়ংক্রিয়ভাবে গ্রহণ করা উচিত৷

পুশডাউন অটোমেটা কি?

একটি পুশডাউন অটোমেটা বা পুশডাউন অটোমেটন বা পিডিএ হল একটি প্রসঙ্গ-মুক্ত ব্যাকরণ প্রয়োগ করার একটি কৌশল যেভাবে আমরা একটি নিয়মিত ব্যাকরণের জন্য ডিটারমিনিস্টিক ফিনিট অটোমেটন বা ডিএফএ ডিজাইন করি। একটি ডিএফএ সীমিত ডেটাতে কাজ করতে পারে, কিন্তু একটি পিডিএ অসীম ডেটাতে কাজ করতে পারে। আমরা পুশডাউন অটোমেটা বুঝতে পারি "সীমাবদ্ধ স্টেটমেশিন" এবং একটি "স্ট্যাক" এর সংমিশ্রণ হিসেবে।

একটি পুশডাউন অটোমেটনের তিনটি উপাদান থাকে -

• একটি ইনপুট টেপ,

• একটি নিয়ন্ত্রণ ইউনিট, এবং

• অসীম আকারের একটি স্ট্যাক।

একটি PDA আনুষ্ঠানিকভাবে 7−tuple (Q, Ʃ, S, δ, q0, I, F) -

• Q হল রাজ্যের সসীম সংখ্যা

• Ʃ হল ইনপুট বর্ণমালা

• S হল স্ট্যাক চিহ্ন

• δ হল ট্রানজিশন ফাংশন:Q × (Ʃ υ {ε}) × S × Q × S*

• q0 হল প্রাথমিক অবস্থা (q0 ε Q)

• I হল প্রাথমিক স্ট্যাক টপ চিহ্ন (I ε S)

• F হল গ্রহণযোগ্য অবস্থার একটি সেট (F ε Q)

আসুন প্রদত্ত ভাষার জন্য একটি পুশডাউন অটোমেটা তৈরি করি −

এই PDA দ্বারা গ্রহণযোগ্য স্ট্রিংগুলি হল −

• 1. 0 ⁿ 2 ⁿ :02, 0022, 000222 ইত্যাদি। 0 এর সংখ্যা সংখ্যার সমান। 2s. যখন m 0 হবে তখন আমাদের কোন 1s থাকবে না। 0s চাপতে থাকুন এবং প্রথম 2 এর সম্মুখীন হওয়ার সাথে সাথে 0s পপ করুন। যদি আমরা স্ট্রিংয়ের শেষে পৌঁছাই এবং 0 সেকেন্ড ছাড়াই স্ট্রিংটি গৃহীত হয়।

• 0 ^m 1 ^m :01, 0011, 000111 ইত্যাদি। 0 এর সংখ্যা সংখ্যার সমান। 1s. যখন n 0 হবে তখন আমাদের কোন 2s থাকবে না। 0s চাপতে থাকুন এবং প্রথম 1 এর সম্মুখীন হওয়ার সাথে সাথে 0s পপ করুন। যদি আমরা স্ট্রিংয়ের শেষে পৌঁছাই এবং 0 সেকেন্ড ছাড়াই স্ট্রিংটি গৃহীত হয়।

• 0 ^n+m 1 ^m 2 ⁿ :0012, 000112, 000122 ইত্যাদি। 0 এর সংখ্যা সংখ্যার যোগফলের সমান। 1s এবং 2s এর। 0s চাপতে থাকুন এবং প্রথম 1 এর সম্মুখীন হলে সেই 0s পপ করুন যতক্ষণ না 1s অবশিষ্ট থাকে। তারপর আবার 0s পুশ করতে থাকুন এবং প্রথম 2 এর সম্মুখীন হলে সেই 0s পপ করুন যতক্ষণ না 2s বাকি থাকে। স্ট্রিংটি গ্রহণ করা হবে৷

• NULL স্ট্রিংও গৃহীত হয়। 0 ⁰ 1 ⁰ 2 ⁰

আসুন মেশিনটি বুঝুন

• q0 রাষ্ট্রের জন্য রূপান্তর :

  • 0, I/0I ) − যদি স্ট্যাকের শীর্ষ I হয় এবং বর্তমান ইনপুট প্রতীক 0 হয় তাহলে স্ট্যাকের শীর্ষে 0 চাপুন এবং q0 এ থাকুন। স্ট্যাক হয়ে যায় 0I...

  • ( 0, 0/00 ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীকটিও 0 হয় তবে স্ট্যাকের শীর্ষে 0 ধাক্কা দিন এবং q0 এ থাকুন। স্ট্যাক 00 হয়ে যায়.... পরবর্তী 1 বা 2 পর্যন্ত 0s চাপতে থাকুন।

  • ( 1, 0/$ ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 1 হয় তাহলে 0 পপ করুন এবং q1 এ যান৷

  • ( 2, 0/$ ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে 0 পপ করুন এবং q2 এ যান৷

  • ( $, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং qf এ যান। NULL স্ট্রিং এর জন্য।

• অবস্থা q1 −

  এর জন্য রূপান্তর

  • ( 1, 0/$ ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 1 হয়, তাহলে 0 থেকে পপ করুন এবং q1-এ থাকুন৷

  • ( $, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং qf এ যান৷

  • ( 2, 0/$ ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে 0 পপ করুন এবং q2 এ যান৷

• q2 −

  অবস্থার জন্য রূপান্তর

  • ( 2, 0/$ ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট চিহ্ন 2 হয় তাহলে 0 পপ করুন এবং q2 এ থাকবেন।

  • ($, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং সেখানে কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং qf এ যান।