আমাদের একটি ভাষা "L" দেওয়া আছে এবং টাস্ক হলো এই ভাষার জন্য একটি পুশডাউন অটোমেটা (PDA) নির্মাণ করা। এই ভাষা ব্যাখ্যা করে যে: 'a' ক্যারেক্টারের ঘটনা 'b' ক্যারেক্টারের ঘটনার দ্বিগুণ, 'c' ক্যারেক্টারের ঘটনা 'd' ক্যারেক্টারের ঘটনার চতুর্গুণ, এবং সব ক্যারেক্টারের ঘটনা ন্যূনতম ১ হবে (যা স্ট্রিংকে NULL ও করতে পারে এবং অটোমেটা tarafından গ্রহণযোগ্য হবে)।
পুশডাউন অটোমেটা কী?
একটি পুশডাউন অটোমেটা বা 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 দ্বারা গ্রহণযোগ্য স্ট্রিংগুলো নিচের রূপের:
- c⁴ⁿdⁿ — ccccd, ccccccccdd, ইত্যাদি। c-এর সংখ্যা d-এর সংখ্যার ৪ গুণ। m=0 হলে a ও b থাকবে না। c গুলো স্ট্যাকে পুশ করতে থাকুন। প্রথম d পাওয়া গেলে স্ট্যাক থেকে ৪টি c পপ করুন। স্ট্রিং শেষে কোনো c বাকি না থাকলে স্ট্রিং গ্রহণযোগ্য।
- a²ᵐbᵐ — aab, aaaabb, ইত্যাদি। a-এর সংখ্যা b-এর সংখ্যার ২ গুণ। n=0 হলে c ও d থাকবে না। a গুলো স্ট্যাকে পুশ করতে থাকুন। প্রথম b পাওয়া গেলে স্ট্যাক থেকে ২টি a পপ করুন। স্ট্রিং শেষে কোনো a বাকি না থাকলে স্ট্রিং গ্রহণযোগ্য।
- a²ᵐc⁴ⁿdⁿbᵐ — aaccccdb, aaaaccccccccddbb। a-এর সংখ্যা b-এর ২ গুণ এবং c-এর সংখ্যা d-এর ৪ গুণ। a ও c পুশ করতে থাকুন। প্রথম d পাওয়া গেলে টপে c থাকলে ৪টি c পপ করুন, তারপর b গুলোর জন্য ২টি a পপ করুন। শেষে কোনো 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 এবং ইনপুট a হলে a পুশ করে q0-এ থাকুন। স্ট্যাক: aa....
- (c, c/c,c) — স্ট্যাক টপ c এবং ইনপুট c হলে c পুশ করে q0-এ থাকুন। স্ট্যাক: cc....
- (b, a/e,aa) — স্ট্যাক টপ a এবং ইনপুট b হলে ২টি a পপ করে q3-এ যান।
- (c, a/c,a) — স্ট্যাক টপ a এবং ইনপুট c হলে c পুশ করে q1-এ যান। স্ট্যাক: ca...
- (d, c/e,cccc) — স্ট্যাক টপ c এবং ইনপুট d হলে ৪টি c পপ করে q4-এ যান।
- ($, I/I, I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে q5-এ যান। NULL স্ট্রিং এর জন্য।
- q1 স্টেটের ট্রানজিশন:
- (c, c/c,c) — স্ট্যাক টপ c এবং ইনপুট c হলে c পুশ করে q1-এ থাকুন।
- (d, c/e,cccc) — স্ট্যাক টপ c এবং ইনপুট d হলে ৪টি c পপ করে q2-এ যান।
- q2 স্টেটের ট্রানজিশন:
- (d, c/e,cccc) — স্ট্যাক টপ c এবং ইনপুট d হলে ৪টি c পপ করে q2-এ থাকুন।
- (b, a/e,aa) — স্ট্যাক টপ a এবং ইনপুট b হলে ২টি a পপ করে q3-এ যান।
- q3 স্টেটের ট্রানজিশন:
- (b, a/e,aa) — স্ট্যাক টপ a এবং ইনপুট b হলে ২টি a পপ করে q3-এ থাকুন।
- ($, I/I, I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে q5-এ যান। NULL স্ট্রিং এর জন্য।
- q4 স্টেটের ট্রানজিশন:
- (d, c/e,cccc) — স্ট্যাক টপ c এবং ইনপুট d হলে ৪টি c পপ করে q4-এ থাকুন।
- ($, I/I, I) — স্ট্যাক টপ I এবং ইনপুট নেই, কিছুই না করে q5-এ যান। NULL স্ট্রিং এর জন্য।
