Pushdown Automata (PDA) হলো এমন এক ধরনের অটোমাটা যা একটি স্ট্যাক মেমোরি ব্যবহার করে, ফলে এটি নেস্টেড বা স্তরবিন্যস্ত গঠন বিশ্লেষণ করতে পারে—যা সাধারণ ফাইনাইট অটোমাটা পারে না। এই কারণে এটি ভাষাতত্ত্বে একটি বিশেষ শ্রেণির ভাষা শনাক্ত করতে ব্যবহৃত হয়।
মূল তথ্যসমূহ:
-
PDA ও Context-Free Grammar (CFG)-এর সম্পর্ক: PDA-এর ক্ষমতা ও CFG-এর ক্ষমতা একেবারে সমান।
-
প্রতিটি Context-Free Language (CFL) একটি PDA দ্বারা শনাক্ত করা যায়।
-
প্রতিটি PDA আবার একটি Context-Free Grammar দ্বারা বর্ণনা করা সম্ভব।
-
-
এই কারণে PDA এবং CFG ভাষাতাত্ত্বিকভাবে সমমান (equivalent) বলে গণ্য হয়।
ভুল বিকল্পসমূহ:
-
ক) Regular Expressions শুধুমাত্র Regular Language তৈরি করে, যা PDA-এর তুলনায় কম শক্তিশালী।
-
গ) Context-Sensitive Grammar PDA-এর চেয়ে বেশি শক্তিশালী, এগুলোর জন্য Linear-Bounded Automata প্রয়োজন।
-
ঘ) Turing Machine সবচেয়ে ক্ষমতাশালী মডেল, যা Recursively Enumerable Language শনাক্ত করতে পারে।
