L ={a(2*m)c(4*n)dnbm এর জন্য পুশডাউন অটোমেটা তৈরি করুন

আমাদের একটি ভাষা "L" দেওয়া হয়েছে এবং কাজটি হল প্রদত্ত ভাষার জন্য একটি পুশডাউন অটোমেটা তৈরি করা যা ব্যাখ্যা করে যে 'a' অক্ষরের সংঘটনগুলি ঘটনার সময় দ্বিগুণ হওয়া উচিত অক্ষর 'b' এবং অক্ষরের 'c' অক্ষরের ঘটনা 'd'-এর সময়ের চারগুণ হওয়া উচিত এবং সমস্ত অক্ষরের সংঘটন ন্যূনতম 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 ={a(2*m)c(4*n)dnbm এর জন্য পুশডাউন অটোমেটা তৈরি করুন | C++ এ m,n =0}

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

ফর্ম

c⁴ⁿ dⁿ − ccccd, ccccccccdd, ইত্যাদি। cs-এর সংখ্যা সংখ্যার 4 গুণ। ds এর। যখন m 0 হবে তখন আমাদের no as এবং bs থাকবে। cs চাপতে থাকুন এবং প্রথম d এর সম্মুখীন হওয়ার সাথে সাথে স্ট্যাক থেকে 4 c পপ করুন। যদি আমরা স্ট্রিংয়ের শেষে পৌঁছায় এবং কোন সিএস ছাড়াই থাকে তাহলে স্ট্রিংটি গৃহীত হয়।
a^2m b^m − aab, aaab, ইত্যাদি। সংখ্যার 2 গুণ সংখ্যা। bs. যখন n 0 হবে তখন আমাদের কোন cs এবং ds থাকবে না। প্রথম b এর সম্মুখীন হওয়ার সাথে সাথে ধাক্কা দিতে থাকুন তারপর স্ট্যাক থেকে 2 b পপ করুন। যদি আমরা স্ট্রিং এর শেষে পৌঁছাই এবং না হিসাবে রেখে দেওয়া হয় তাহলে স্ট্রিংটি গৃহীত হবে।
a^2m c⁴ⁿ dⁿ b^m − aaccccdb, aaacccccccddbb. এর সংখ্যা 2 গুণ সংখ্যা। bs এবং cs এর 4 গুণ ds সংখ্যার সমান। হিসাবে এবং cs ঠেলাঠেলি রাখুন. যত তাড়াতাড়ি প্রথম d সম্মুখীন হয় তারপর পপ 4 cs যদি এটি উপরে থাকে এবং তারপর পপ 2 বাকি bs হিসাবে। যদি আমরা শেষ পর্যন্ত পৌঁছায় এবং কোন a বাকি না থাকে তাহলে স্ট্রিংটি গৃহীত হয়।
NULL স্ট্রিংও গৃহীত হয়। a⁰ c⁰ d⁰ b⁰ .

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

অবস্থা q0 −
এর জন্য রূপান্তর
- (a, I/a,I ) − যদি স্ট্যাকের শীর্ষ I হয় এবং বর্তমান ইনপুট প্রতীক a হয় তাহলে স্ট্যাকের শীর্ষে a চাপুন এবং q0 এ থাকুন। স্ট্যাক হয়ে যায় aI…
- ( c, I/c,I ) − যদি স্ট্যাকের শীর্ষ I হয় এবং বর্তমান ইনপুট চিহ্নটি হয় c তাহলে স্ট্যাকের শীর্ষে c চাপুন এবং q0 এ থাকুন। স্ট্যাক হয়ে যায় cI...
- ( a, a/a,a ) − যদি স্ট্যাকের শীর্ষ একটি হয় এবং বর্তমান ইনপুট প্রতীকটিও একটি হয় তবে স্ট্যাকের শীর্ষে a চাপুন এবং q0 এ থাকুন। স্ট্যাক AA হয়ে যায়.... তারপরে c বা b না হওয়া পর্যন্ত চাপ দিতে থাকুন।
- ( c, c/c,c ) − যদি স্ট্যাকের শীর্ষটি হয় c এবং বর্তমান ইনপুট চিহ্নটিও c হয় তবে স্ট্যাকের টপ সি পুশ করুন এবং q0 এ থাকুন। স্ট্যাক cc হয়ে যায়.... পরবর্তী d পর্যন্ত cs চাপতে থাকুন।
- ( b, a/e,aa ) − যদি স্ট্যাকের উপরে হয় a এবং বর্তমান ইনপুট প্রতীক b হয় তাহলে স্ট্যাক থেকে 2 পপ করুন এবং q3 এ যান।
- (c, a/c,a ) − যদি স্ট্যাকের শীর্ষ a হয় এবং বর্তমান ইনপুট প্রতীক হয় c তাহলে স্ট্যাকের শীর্ষে c চাপুন এবং q1 এ যান। স্ট্যাক হয়ে যায় ca...
- ( d, c/e,cccc ) − যদি স্ট্যাকের শীর্ষটি হয় c এবং বর্তমান ইনপুট প্রতীক d হয় তাহলে স্ট্যাক থেকে 4 ds পপ করুন এবং q4 এ যান৷
- ($, I/I, I) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q5 এ যান। NULL স্ট্রিং এর জন্য।
অবস্থা q1 −
এর জন্য রূপান্তর
- ( c, c/c,c ) − যদি স্ট্যাকের শীর্ষে হয় c এবং বর্তমান ইনপুট প্রতীকটিও c হয়, তাহলে স্ট্যাকের শীর্ষে c চাপুন এবং q1 এ থাকুন। স্ট্যাক cc হয়ে যায়.... পরবর্তী d পর্যন্ত cs চাপতে থাকুন।
- ( d, c/e,cccc ) − যদি স্ট্যাকের শীর্ষটি হয় c এবং বর্তমান ইনপুট প্রতীক d হয় তাহলে স্ট্যাক থেকে 4 ds পপ করুন এবং q2 এ যান৷
q2 −
অবস্থার জন্য রূপান্তর
- ( d, c/e,cccc ) − যদি স্ট্যাকের শীর্ষটি হয় c এবং বর্তমান ইনপুট প্রতীক d হয় তাহলে স্ট্যাক থেকে 4 ds পপ করুন এবং q2 এ যান৷
- ( b, a/e,aa ) − যদি স্ট্যাকের উপরে হয় a এবং বর্তমান ইনপুট প্রতীক b হয় তাহলে স্ট্যাক থেকে 2 পপ করুন এবং q3 এ যান।
অবস্থা q3 −
এর জন্য রূপান্তর
- ( b, a/e,aa ) − যদি স্ট্যাকের শীর্ষ a হয় এবং বর্তমান ইনপুট চিহ্ন b হয় তাহলে স্ট্যাক থেকে 2 পপ করুন এবং q3 এ থাকুন।
- ( $, I/I, I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q5 এ যান। NULL স্ট্রিং এর জন্য।
অবস্থা q4 −
এর জন্য রূপান্তর
- ( d, c/e,cccc ) − যদি স্ট্যাকের শীর্ষটি হয় c এবং বর্তমান ইনপুট প্রতীক d হয় তাহলে স্ট্যাক থেকে 4 ds পপ করুন এবং q4 এ থাকবেন।
- ( $, I/I, I ) − যদি স্ট্যাকের শীর্ষে I হয় এবং কোনো ইনপুট না থাকে তাহলে কিছুই করবেন না এবং q5 এ যান। NULL স্ট্রিং এর জন্য।