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

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

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

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

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

একটি ইনপুট টেপ,
একটি নিয়ন্ত্রণ ইউনিট, এবং
অসীম আকারের একটি স্ট্যাক।

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

হিসাবে বর্ণনা করা যেতে পারে

Q হল রাজ্যের সসীম সংখ্যা
Σ হল ইনপুট বর্ণমালা
S হল স্ট্যাক চিহ্ন
δ হল ট্রানজিশন ফাংশন:Q × (Σ υ {ε}) × S × Q × S*
q0 হল প্রাথমিক অবস্থা (q0 Ε Q)
I হল প্রাথমিক স্ট্যাক টপ চিহ্ন (I Ε S)
F হল গ্রহণযোগ্য অবস্থার একটি সেট (F Ε Q)

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

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

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

ফর্ম

0ⁿ 3ⁿ − 03, 0033, 000333 ইত্যাদি। 0 এর সংখ্যা সংখ্যার সমান। 3s. m 0 হলে আমাদের 1s এবং 2s থাকবে না। 0s চাপতে থাকুন এবং প্রথম 3 এর সম্মুখীন হওয়ার সাথে সাথে 0s পপ করুন। যদি আমরা স্ট্রিংয়ের শেষে পৌঁছাই এবং 0 সেকেন্ড ছাড়াই স্ট্রিংটি গৃহীত হয়।
1^m 2^m − 12, 1122, 111222 ইত্যাদি। 1s এর সংখ্যা সংখ্যার সমান। 2s. যখন n 0 হবে তখন আমাদের কোন 0s এবং 3s থাকবে না। 1s পুশ করতে থাকুন এবং প্রথম 2 এর সম্মুখীন হওয়ার সাথে সাথে পপ 1s। যদি আমরা স্ট্রিং এর শেষে পৌছাই এবং কোন 1s না থাকে তাহলে স্ট্রিংটি গৃহীত হবে৷
0ⁿ 1^m 2^m 3ⁿ − 0123, 001233, 011223 ইত্যাদি। 0 এর সংখ্যা সংখ্যার সমান। 3s এবং 1s এর সমান 2s। 0 এবং 1 সেকেন্ড চাপতে থাকুন। যত তাড়াতাড়ি প্রথম 2 সম্মুখীন হয় তারপর পপ 1s যদি এটি শীর্ষে থাকে এবং তারপর বাকি 3s এর জন্য 0s পপ করুন৷ যদি আমরা শেষ পর্যন্ত পৌঁছায় এবং কোন 0 বাকি না থাকে তাহলে স্ট্রিংটি গৃহীত হয়।
NULL স্ট্রিংও গৃহীত হয়। 0⁰ 1⁰ 2⁰ 3⁰ .

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

অবস্থা q0 −
এর জন্য রূপান্তর
- ( 0, I/0,I ) − যদি স্ট্যাকের শীর্ষ I হয় এবং বর্তমান ইনপুট প্রতীক 0 হয় তাহলে স্ট্যাকের শীর্ষে 0 চাপুন এবং q0 এ থাকুন। স্ট্যাক হয়ে যায় 0I...
- ( 0, 0/0,0 ) − যদি স্ট্যাকের শীর্ষটি 0 হয় এবং বর্তমান ইনপুট প্রতীকটিও 0 হয় তবে স্ট্যাকের শীর্ষে 0 ধাক্কা দিন এবং q0 এ থাকুন। স্ট্যাক 00 হয়ে যায়.... পরবর্তী 1 বা 3 পর্যন্ত 0 সেকেন্ড চাপতে থাকুন।
- ( 1, 0/1,0 ) − যদি স্ট্যাকের শীর্ষটি 0 হয় এবং বর্তমান ইনপুট প্রতীক 1 হয় তবে স্ট্যাকের শীর্ষে 1 ধাক্কা দিন এবং q1 এ যান। স্ট্যাক হয়ে যায় 10...
- ( 1, I/1,I ) − যদি স্ট্যাকের উপরে I হয় এবং বর্তমান ইনপুট প্রতীক 1 হয় তাহলে 1 চাপুন এবং q5 এ যান।
- ( 3, 0/e ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 3 হয় তাহলে 0 পপ করুন এবং q3 এ যান৷
- ( $, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q4 এ যান। NULL স্ট্রিং এর জন্য।
অবস্থা q1 −
এর জন্য রূপান্তর
- ( 1, 1/11 ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট চিহ্নটিও 1 হয় তবে স্ট্যাকের শীর্ষে 1 টিপুন এবং q1 এ থাকুন। স্ট্যাক 11 হয়ে যায়.... তারপর পরবর্তী 2 পর্যন্ত 1s পুশ করতে থাকুন।
- ( 2, 1/e ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে 1 পপ করুন এবং q2 এ যান৷
q2 −
অবস্থার জন্য রূপান্তর
- ( 2, 1/e ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে পপ 1 এবং q2-তে থাকবে।
- ( 3, 0/e ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট প্রতীক 3 হয় তাহলে 0 পপ করুন এবং q3 এ যান৷
অবস্থা q3 −
এর জন্য রূপান্তর
- ( 3, 0/e ) − যদি স্ট্যাকের শীর্ষ 0 হয় এবং বর্তমান ইনপুট চিহ্ন 3 হয় তাহলে 1 পপ করুন এবং q3 এ থাকবেন।
- ( $, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q4 এ যান। NULL স্ট্রিং এর জন্য।
অবস্থা q5 −
এর জন্য রূপান্তর
- ( 1, 1/1,1 ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট প্রতীকটিও 1 হয় তবে স্ট্যাকের শীর্ষে 1 ধাক্কা দিন এবং q5 এ থাকুন। স্ট্যাক 11 হয়ে যায়.... তারপর পরবর্তী 2 পর্যন্ত 1s পুশ করতে থাকুন।
- ( 2, 1/e ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে 1 পপ করুন এবং q6 এ যান৷
অবস্থা q6 −
এর জন্য রূপান্তর
- ( 2, 1/e ) − যদি স্ট্যাকের শীর্ষ 1 হয় এবং বর্তমান ইনপুট প্রতীক 2 হয় তাহলে পপ 1 এবং q6-এ থাকবে।
- ( $, I/I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q4 এ যান। NULL স্ট্রিং এর জন্য।