L = {0⁽ⁿ⁺ᵐ⁾1ᵐ2ⁿ | m,n = 0} ভাষার জন্য পুশডাউন অটোমেটা নির্মাণ C++-এ

আমাদের একটি ভাষা "L" দেওয়া আছে এবং টাস্ক হলো এই ভাষার জন্য একটি পুশডাউন অটোমেটা (PDA) নির্মাণ করা। এই ভাষা ব্যাখ্যা করে যে: ০-এর ঘটনা হবে ১ এবং ২-এর ঘটনার যোগফল, এবং ১ ও ২-এর ঘটনা ন্যূনতম ১ (যা স্ট্রিংকে NULL ও করতে পারে এবং অটোমেটা দ্বারা গ্রহণযোগ্য হবে)।

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

একটি পুশডাউন অটোমেটা বা PDA হলো একটি কনটেক্সট-ফ্রি গ্রামার বাস্তবায়নের টেকনিক, যেমন আমরা রেগুলার গ্রামারের জন্য ডিটারমিনিস্টিক ফাইনিট অটোমেটা (DFA) ডিজাইন করি। DFA ফাইনিট ডেটায় অপারেট করতে পারে, কিন্তু PDA অনন্ত ডেটায় অপারেট করতে পারে। PDA কে "ফাইনিট স্টেট মেশিন" এবং একটি "স্ট্যাক"-এর কম্বিনেশন হিসেবে বোঝা যায়।

একটি PDA কে رسمیভাবে ৭-টাপল (Q, Σ, S, δ, q0, I, F) হিসেবে বর্ণনা করা যায়:

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

দেওয়া ভাষার জন্য পুশডাউন অটোমেটা নির্মাণ:

এই PDA দ্বারা গ্রহণযোগ্য স্ট্রিংগুলো নিচের রূপের:

• 0ⁿ2ⁿ — 02, 0022, 000222 ইত্যাদি। ০-এর সংখ্যা = ২-এর সংখ্যা। m=0 হলে ১ থাকবে না। ০ পুশ করুন, প্রথম ২ পাওয়া গেলে ০ পপ করুন। শেষে কোনো ০ বাকি না থাকলে গ্রহণযোগ্য।
• 0ᵐ1ᵐ — 01, 0011, 000111 ইত্যাদি। ০-এর সংখ্যা = ১-এর সংখ্যা। n=0 হলে ২ থাকবে না। ০ পুশ করুন, প্রথম ১ পাওয়া গেলে ০ পপ করুন। শেষে কোনো ০ বাকি না থাকলে গ্রহণযোগ্য।
• 0⁽ⁿ⁺ᵐ⁾1ᵐ2ⁿ — 0012, 000112, 000122 ইত্যাদি। ০-এর সংখ্যা = ১ ও ২-এর সংখ্যার যোগফল। ০ পুশ করুন, প্রথম ১ পাওয়া গেলে ০ পপ করুন যতক্ষণ ১ বাকি থাকে। আবার ০ পুশ করুন, প্রথম ২ পাওয়া গেলে ০ পপ করুন যতক্ষণ ২ বাকি থাকে। স্ট্রিং গ্রহণযোগ্য হবে।
• NULL স্ট্রিং — 0⁰1⁰2⁰ ও গ্রহণযোগ্য।

মেশিনটি বোঝা যাক

• q0 স্টেটের ট্রানজিশন:
  • (0, I/0I) — স্ট্যাক টপ I এবং ইনপুট 0 হলে 0 পুশ করে q0-এ থাকুন। স্ট্যাক: 0I...
  • (0, 0/00) — স্ট্যাক টপ 0 এবং ইনপুট 0 হলে 0 পুশ করে q0-এ থাকুন। স্ট্যাক: 00....
  • (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-এ যান।