আমাদের একটি ভাষা "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ⁿ3ⁿ — 03, 0033, 000333 ইত্যাদি। ০-এর সংখ্যা = ৩-এর সংখ্যা। m=0 হলে ১ ও ২ থাকবে না। ০ গুলো পুশ করুন, প্রথম ৩ পাওয়া গেলে ০ পপ করুন। শেষে কোনো ০ বাকি না থাকলে গ্রহণযোগ্য।
- 1ᵐ2ᵐ — 12, 1122, 111222 ইত্যাদি। ১-এর সংখ্যা = ২-এর সংখ্যা। n=0 হলে ০ ও ৩ থাকবে না। ১ গুলো পুশ করুন, প্রথম ২ পাওয়া গেলে ১ পপ করুন। শেষে কোনো ১ বাকি না থাকলে গ্রহণযোগ্য।
- 0ⁿ1ᵐ2ᵐ3ⁿ — 0123, 001233, 011223 ইত্যাদি। ০=৩ এবং ১=২। ০ ও ১ পুশ করুন। প্রথম ২ পাওয়া গেলে টপে ১ থাকলে ১ পপ করুন, তারপর ৩ গুলোর জন্য ০ পপ করুন। শেষে কোনো ০ বাকি না থাকলে গ্রহণযোগ্য।
- 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, 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, 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 হলে 0 পপ করে q3-এ থাকুন।
- ($, I/I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে q4-এ যান। NULL স্ট্রিং এর জন্য।
- q5 স্টেটের ট্রানজিশন:
- (1, 1/1,1) — স্ট্যাক টপ 1 এবং ইনপুট 1 হলে 1 পুশ করে q5-এ থাকুন। স্ট্যাক: 11....
- (2, 1/e) — স্ট্যাক টপ 1 এবং ইনপুট 2 হলে 1 পপ করে q6-এ যান।
- q6 স্টেটের ট্রানজিশন:
- (2, 1/e) — স্ট্যাক টপ 1 এবং ইনপুট 2 হলে 1 পপ করে q6-এ থাকুন।
- ($, I/I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে q4-এ যান। NULL স্ট্রিং এর জন্য।
