আমাদের একটি ভাষা "L" দেওয়া আছে এবং টাস্ক হলো এই ভাষার জন্য একটি পুশডাউন অটোমেটা (PDA) নির্মাণ করা। এই ভাষা ব্যাখ্যা করে যে: ১-এর ঘটনা হবে ০ এবং ২-এর ঘটনার যোগফল, এবং ০ ও ২-এর ঘটনা ন্যূনতম ১ (যা স্ট্রিংকে NULL ও করতে পারে এবং অটোমেটা দ্বারা গ্রহণযোগ্য হবে)।
পুশডাউন অটোমেটা কী?
একটি পুশডাউন অটোমেটা বা PDA হলো একটি কনটেক্সট-ফ্রি গ্রামার বাস্তবায়নের টেকনিক, যেমন আমরা রেগুলার গ্রামারের জন্য ডিটারমিনিস্টিক ফাইনিট অটোমেটা (DFA) ডিজাইন করি। DFA ফাইনিট ডেটায় অপারেট করতে পারে, কিন্তু PDA অনন্ত ডেটায় অপারেট করতে পারে। 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ᵐ1ᵐ — 01, 0011, 000111 ইত্যাদি। ০-এর সংখ্যা = ১-এর সংখ্যা। n=0 হলে ২ থাকবে না। ০ পুশ করুন, প্রথম ১ পাওয়া গেলে ০ পপ করুন। শেষে কোনো ০ বাকি না থাকলে গ্রহণযোগ্য।
- 1ⁿ2ⁿ — 12, 1122, 111222 ইত্যাদি। ১-এর সংখ্যা = ২-এর সংখ্যা। m=0 হলে ০ থাকবে না। ১ পুশ করুন, প্রথম ২ পাওয়া গেলে ১ পপ করুন। শেষে কোনো ১ বাকি না থাকলে গ্রহণযোগ্য।
- 0ⁿ1⁽ᵐ⁺ⁿ⁾2ᵐ — 0112, 001112, 001112 ইত্যাদি। ১-এর সংখ্যা = ০ ও ২-এর সংখ্যার যোগফল। ০ পুশ করুন, প্রথম ১ পাওয়া গেলে ০ পপ করুন যতক্ষণ ০ বাকি থাকে। আবার ১ পুশ করুন যতক্ষণ প্রথম ২ পাওয়া যায়। তারপর প্রতিটি ২-এর জন্য ১ পপ করুন যতক্ষণ ১ বাকি থাকে। শেষে কোনো ১ বাকি না থাকলে গ্রহণযোগ্য।
- NULL স্ট্রিং — 0⁰1⁰2⁰ ও গ্রহণযোগ্য।
মেশিনটি বোঝা যাক
- q0 স্টেটের ট্রানজিশন:
- (0, I/0I) — স্ট্যাক টপ I এবং ইনপুট 0 হলে 0 পুশ করে q0-এ থাকুন। স্ট্যাক: 0I...
- (0, 0/00) — স্ট্যাক টপ 0 এবং ইনপুট 0 হলে 0 পুশ করে q0-এ থাকুন। স্ট্যাক: 00....
- (1, I/1I) — স্ট্যাক টপ I এবং ইনপুট 1 হলে 1 পুশ করে q1-এ যান। স্ট্যাক: 1I...
- (1, 0/$) — স্ট্যাক টপ 0 এবং ইনপুট 1 হলে 0 পপ করে q1-এ যান।
- (1, 0/$) — স্ট্যাক টপ 0 এবং ইনপুট 1 হলে 0 পপ করে q1-এ যান।
- q1 স্টেটের ট্রানজিশন:
- (1, 1/11) — স্ট্যাক টপ 1 এবং ইনপুট 1 হলে 1 পুশ করে q1-এ থাকুন। স্ট্যাক: 11....
- (1, 0/$) — স্ট্যাক টপ 0 এবং ইনপুট 1 হলে 0 পপ করে q1-এ থাকুন।
- ($, I/I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে qf-এ যান।
- (2, 1/$) — স্ট্যাক টপ 1 এবং ইনপুট 2 হলে 1 পপ করে q2-এ যান।
- q2 স্টেটের ট্রানজিশন:
- (2, 1/$) — স্ট্যাক টপ 1 এবং ইনপুট 2 হলে 1 পপ করে q2-এ থাকুন।
- ($, I/I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে qf-এ যান।
